二分検索【PHP】
二文検索
二分検索:
配列の中央値が検索している数値より大なりか、小なりかによって検索範囲を狭めていき、値があるかどうかを調べるもの
- 静的メソッドbinarysearchは引数として$arrと$numを持つ。$arrはランダムな数字の配列。$numは探したい数字。
- $lowは探索範囲の始まりのキーを示す。一方、$highは探索範囲の終わりのキーを指す。
- while文内を見ていく。$midは探索範囲の真ん中のキーを指す。
- もし$mid番目に対応する値が$numであるなら、$midを返して、繰り返しから抜ける。
- もし中央の要素$arr[$mid]が$numより小さい場合は、探したいキーは中央の要素よりも右にある。探索範囲のはじまりのキー,つまり$lowを$mid + 1に置き換え、中央の要素 + 1から右を探すことになる。
- もし中央の要素$arr[$mid]が$numより大きいときは探索範囲の終わり$highを$mid - 1に置き換え,中央の要素 - 1から左を探すことになる。
- 繰り返し行い、$midをキーとした要素が求まれば、検索成功。nullであれ該当の値は存在しない。
