【1日目】二分探索とはなんぞや
アルゴリズムの中で考え方としても汎用性が高く、高速に動くものとしての代表として二分探索がある。
これは考え方自体がかなりシンプル。ソートされたデータに対して使うことができる。
例えばlist = [1,3,5,7,9]の配列があったとする。その中から7を探すにはどうしたらいいか？
まず思いつくのは前から順番に比較していく方法が考えられる。しかし、これはlistの中身が5つくらいなら早いが、10万になってしまうと１つずつ比較することになり時間がかかる。
ではどうすれば早くなるだろうか。真ん中の数字と比較して大きいか小さいかを判断すればいい。
大きければ真ん中より小さい数はもう考える必要がなくなる。
[1,2,3,4,5]だとして4を探すなら3より4は大きいので、残りは4,5だけになる。これを見つかるまで繰り返すだけである。
要素がいくつになろうが繰り返す。これだけである。もちろんない場合もあるのでそれも考えなくてはならない。
ない場合を考えなかったら3より大きいけど5より小さいをいくら繰り返しても見つからないことになってしまう。
参考サイトは下記に載せておくのでとりあえずコードを書いていく。
def binary_search(list,item): low = 0 high = len(list) - 1 while low <= high: mid = (low + high) // 2 guess = list[mid] if guess == item: return mid elif guess < item: low = mid + 1 else: high = mid - 1 return None
これでとりあえず実行できる。一番オーソドックスなものである。
以上です。ありがとうございます😊
