バイナリサーチ[binary search]

・用語のポイント

- 検索の方法の名前

- 「二分探索」とも呼ばれる

- 配列から高速に候補を絞り込む

- データが順番に並んでいる必要がある

- ひとつひとつ調べていく探索法としてリニアサーチ（線形探索法）と呼ばれるものがある

順番に並んでいるデータから中央値を取り出し、探しているデータが取り出した中央値より大きいか小さいか比べ中央値の前後で存在をチェックする

存在しない方を削除し再び中央値を取り出し同じ操作を繰り返し目的のデータを見つける

・イメージ

・Pythonコード例

# idのkeyでsortされたdata_listを用意
data_list = [{"id": "1"}, {"id": "2"}, {"id": "3"}, {"id": "4"}]
# idが2のオブジェクトを取得する
key = 2

def binary_search(arr, min, max, x, item):
  if max >= min:
      i = int(min + (max - min) / 2)  # average
      if arr[i][item] == x:
          return arr[i]
      elif arr[i][item] < x:
          return binary_search(arr, i + 1, max, x, item)
      else:
          return binary_search(arr, min, i - 1, x, item)
  return None

target_data = binary_search(data_list, 0, len(
                            data_list) - 1, key, "id")
# target_dataには{"id": "2"}が入る