binarySearch.php
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
<?php class Algorithm { static function binarySearch( $arr, $num ) { $trials = 1; // 試行回数 $low = 0; // 最小範囲 $high = count( $arr ) - 1; // 最大範囲 while( $low <= $high ) { $pivot = ($low + $high) / 2; $pivot = (int)$pivot; if($arr[$pivot] == $num) { return array( $num, $trials ); } if($num > $arr{$pivot}) { $low = $pivot + 1; } if($num < $arr{$pivot}) { $high = $pivot -1; } ++$trials; } return null; } } // ------------------------------------------------------------ $arr = array( 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ); $num = 8; // ------------------------------------------------------------ $anser = Algorithm::binarySearch( $arr, $num ); var_dump($anser); echo "<hr/>"; echo "ナンバー:{$anser[0]} <br/>"; echo "試行回数:{$anser{1}} <br/>"; |
表示結果
|
1 2 3 4 |
array(2) { [0]=> int(8) [1]=> int(4) } ナンバー:8 試行回数:4 |