TL;DR
- 基礎的な点でありますが、しっかり頭に入れておくためPythonで二分探索のコードを書いたり説明をまとめたりしていきます。
- 勉強のため自前でコードを書いて進めます（二分探索用の標準モジュールなどは使わずに）。
- 元々デザイン方面の学校卒なので、コンピューターサイエンス方面で知識的に雑な点などはご容赦ください。
つかうもの
- Python 3.8.5
- VS Code
二分探索とは
二分探索とはソート済みの配列に対する値の検索のアルゴリズムの一つです。
バイナリサーチ（binary search）とも呼ばれます。
検索対象の配列がソート済みという条件が付きますが、通常の検索よりも対象のリストが巨大になっても検索が遅くなりにくいという性質を持ちます。
方法としては、まずリストの中央に位置している値を取得し、その中央の値が検索対象の値と比べて大きいのか小さいのかを比較します。
検索対象の値が配列の中央の値よりも小さい場合には、今度は左端から中央の値の手前の範囲に配列の範囲を絞り込みます。
逆に検索対象の値が中央の値よりも大きい場合には今度は中央の値の1つ右の値から配列の右端までの範囲に配列の範囲を絞り込みます。
その後は絞り込んだ配列の範囲でさらに中央の値を取り、再び検索対象の値が中央の値よりも大きいか小さいかを判定し、配列を絞り込みます。
もし検索対象の値と配列の中央の値が一致した場合、対象の値が見つかったことになるのでそこで検索が終了です。
[1, 1, 2, 3, 3, 4, 5, 6, 6, 7, 8]というソート済みのリストで2の値を検索するようなケースを考えてみます。
まずはリストの中央の値を取得します。最初の中央の値は4です。
検索対象の値の2は中央の値の4よりも小さいため、リストを4の部分よりも左側に絞りこみ、[1, 1, 2, 3, 3]という値にします。
絞り込んだ後のリストで再度中央の値を取得します。今度はリストの中央の値が2となっています。これは検索対象の2と一致ずるため、対象が存在するという判定で検索が終了します。
通常の検索との計算オーダーの比較
通常の検索処理は先頭から順番に一致するか検索を実施します。計算オーダーは$O(n)$（ただし、検索対象の値が先頭の方に存在すればもっと少なくなります）となり、配列の件数（$n$）が大きくなればなるほど線形で処理時間が長くなっていきます。
一方で二分探索の場合には計算オーダーは$O(log_2 n)$となるため、配列のサイズが大きくなっても処理時間がひたすら肥大化する・・・といったことは軽減されます。
どういった時に使えるのか
通常の検索よりも二分探索の方が処理が速くなる一方で、二分探索にはソートされている配列でのみしか使えません（ソートされていないと配列を分割時に大小関係がおかしなことになります）。
そのため検索対象の配列がソートされておらず、且つ検索が1回しか実行しない・・・といったケースだと通常の検索よりもソートの方が計算コストが高くなってしまい、二分探索を使うメリットはありません。
一方で配列が既にソート済みの場合や、もしくはなんども検索処理を繰り返す場合などにはソートを実行しても二分探索を使った方が計算コストが低く抑えられます。
Pythonで自分で書いてみる
文字などのリストでも数値と同様に二分探索を使ったりはできますが、今回は整数を格納するリストでサンプルとして進めます。
また、検索結果のインデックスを返すといった制御ではなくシンプルにリストに値が含まれるかを調べる形で進めます。
from typing import List
list_value: List[int] = [
100, 23, 33, 51, 70, 32, 34, 13, 3, 79, 8, 12, 16, 134, 83]
sorted_list: List[int] = sorted(list_value)
def binary_search(sorted_list: List[int], search_value: int) -> bool:
"""
二分探索を実施し、検索対象の値がリスト内に含まれるかどうかの
真偽値を取得する。
Parameters
----------
sorted_list : list of int
ソート済みの整数値を格納したリスト。
search_value : int
検索対象の値。
Returns
-------
value_exists : bool
値がリスト内に含まれるかどうか。
"""
left_index: int = 0
right_index: int = len(sorted_list) - 1
while left_index <= right_index:
middle_index: int = (left_index + right_index) // 2
middle_value: int = sorted_list[middle_index]
if search_value < middle_value:
right_index = middle_index - 1
continue
if search_value > middle_value:
left_index = middle_index + 1
continue
return True
return False
順番にコードに触れていきます。
まずは二分探索では対象のリストはソートしてある必要があるため、sorted関数を使ってリストをソートしています（sortメソッドなどでも変わりありません）。
list_value: List[int] = [
100, 23, 33, 51, 70, 32, 34, 13, 3, 79, 8, 12, 16, 134, 83]
sorted_list: List[int] = sorted(list_value)
続いて二分探索の関数の処理です。
left_index: int = 0
right_index: int = len(sorted_list) - 1
対象とするリストのインデックス範囲を扱うための変数をleft_indexとright_indexとして設定しています。リストの左端のインデックスをleft_index、右端をright_indexとしています。これらの値はループで検索が終わるまで、二分されるたびに片側を更新していきます。
while left_index <= right_index:
二分する処理はwhileのループで繰り返し実行します。このループは左端のインデックスが右端のインデックスよりも左にあるかもしくは同じインテックスである限り繰り返します。もし右端のインデックスよりも右になった場合は対象とするリストの範囲が無くなった（全ての対象を検索し終わった）状態となるので、そこでループを終了し対象が見つからなかったとして判定します。
middle_index: int = (left_index + right_index) // 2
middle_value: int = sorted_list[middle_index]
ループ内でのmiddle_indexは対象の配列範囲の中の中央の値を格納しています。// 2で2で割って端数を切り捨てています（//は除算に加えてfloor的な挙動になります）。
また、中央のインデックスだけでなくそのインデックスを参照して中央の値を変数に設定もしています（middle_value）。
if search_value < middle_value:
right_index = middle_index - 1
continue
if文で、もし検索対象の値が中央の値よりも小さければ配列を左半分のみに二分するため、右端のインデックス（right_index）を中央のインデックスの左隣りに設定しています（middle_index - 1）。
※if文の判定で中央の値自体は対象ではないことは分かっているので、中央のインデックスではなく-1したインデックスを設定します。
if search_value > middle_value:
left_index = middle_index + 1
continue
反対に検索対象の値が中央の値よりも大きい場合には配列を右半分のみになるように左端のインデックス（left_index）の値を調整します。
return True
検索対象の値が中央の値よりも小さくも大きくも無い場合、つまり中央の値と同一の場合には、検索対象の値が存在するとしてTrueを返却しています。
return False
実際に実行してみます。まずは対象がリスト内に存在する条件から試してみます。
value_exists = binary_search(
sorted_list=sorted_list,
search_value=83)
print(value_exists)
True
正常にTrueが返ってきました。続いて検索対象がリストに含まれない条件を指定してみます。
value_exists = binary_search(
sorted_list=sorted_list,
search_value=84)
print(value_exists)
False
こちらも想定通りFalseとなりました。