togatttiのエンジニアメモ

過度な期待はしないでください。旧麹町で働くエンジニアのメモ帳です。

二分検索【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であれ該当の値は存在しない。

おまけ:ボゴソート

変わり種のアルゴリズムとしてボゴソートなるものがある。

  • ランダムな数字からなる配列を用意。
  • その中から一つずつ要素を取り出す。
  • 取り出した順番に要素がソートされていなければ、

やり直しで最初から試行を繰り返す。

トランプをばらまいて、その中から一枚ずつ選んでいって順番通りに並ぶまで、引き続ける感じ。
考えたら途方もない作業。配列の要素数を一定以上増やすと結果がかえってこなかった...

参考