1120_バイナリーサーチについて

https://sl.bing.net/gxTEm7GxnCC

Q.1

バイナリーサーチについて詳しく教えて下さい。

A.1

バイナリーサーチは、ソート済みの配列から目的の値を高速に見つけるアルゴリズムです。配列の中央の要素と目的の値を比較して、目的の値が中央の要素より大きいか小さいかを判断します。大きい場合は、配列の右半分に目的の値があるとわかります。小さい場合は、配列の左半分に目的の値があるとわかります。このようにして、探索範囲を半分に絞り込んでいきます。目的の値が見つかるか、探索範囲がなくなるまで繰り返します。

バイナリーサーチの計算量は、配列の長さをnとすると、O(log n)です。これは、一回の操作で探索範囲が半分になるため、最大でlog n回の操作で目的の値が見つかるかどうかがわかるからです。バイナリーサーチは、線形探索のO(n)よりもはるかに効率的です。

バイナリーサーチの具体的な例として、Pythonでの実装を紹介します。³の記事にあるコードを参考にしました。

def binary_search(l, value):
  low = 0
  high = len(l) - 1
  while low <= high:
    mid = (low + high) // 2
    if l[mid] == value:
      print('Found')
      return True
    elif l[mid] < value:
      low = mid + 1
    else:
      high = mid - 1
  print('Not Found')
  return False

# テスト
l = [1, 2, 3, 4, 5, 6, 7] # ソート済みの配列
print(binary_search(l, 5)) # 出力はTrue
print(binary_search(l, 8)) # 出力はFalse

バイナリーサーチについて、詳しくは¹や²や⁴をご覧ください。

ソース: Bing との会話 2023/11/11 (1) Algorithm | 二分探索をPython3で解説（例題あり） - Qiita. https://qiita.com/uniTM/items/2f2a38f225f04154df9a. (2) 二分探索(Binary Search)のアルゴリズム | アルゴリズムロジック. https://algo-logic.info/binary-search/. (3) バイナリーサーチ／二分探索 : アルゴリズム. https://www.codereading.com/algo_and_ds/algo/binary_search.html. (4) 二分探索（2分探索 / バイナリサーチ）とは - 意味をわかり .... https://e-words.jp/w/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2.html. (5) github.com. https://github.com/yamarkz/competition/tree/b867513f8328608878ce3969500774e864a9fa3d/python%2Fbinary_search.py.

Q.2

効率の良いサーチアルゴリズムは、他にどんなものがありますか？

A.2

効率の良いサーチアルゴリズムは、データの量や性質によって異なりますが、一般的には以下のようなものがあります。

• 最良優先探索³：評価関数に基づいて、最も有望なノードから探索を進める方法です。目的ノードに近いと思われるノードを優先的に探索することで、無駄な探索を減らすことができます。最良優先探索の例としては、ダイクストラ法³やA*アルゴリズム³や均一コスト探索³を挙げることができます。
• 幅優先探索：始点から近いノードから順に探索する方法です。始点からの距離が同じノードは、すべて探索した後に次の距離のノードに移ることで、最短経路を見つけることができます。幅優先探索は、木構造やグラフ構造の探索に適しています。
• 深さ優先探索：始点から遠いノードまで探索を進める方法です。探索したノードから枝分かれするノードがあれば、その中の一つを選んでさらに探索を進めます。枝分かれするノードがなくなったら、一つ前のノードに戻って別のノードを探索します。深さ優先探索は、解の候補を絞り込むのに適しています。

以上のように、効率の良いサーチアルゴリズムは、目的や条件に応じて選択することが重要です。詳しくは¹や²や⁴や⁵をご覧ください。

ソース: Bing との会話 2023/11/11 (1) 最良優先探索 - Wikipedia. https://bing.com/search?q=%e5%8a%b9%e7%8e%87%e3%81%ae%e8%89%af%e3%81%84%e3%82%b5%e3%83%bc%e3%83%81%e3%82%a2%e3%83%ab%e3%82%b4%e3%83%aa%e3%82%ba%e3%83%a0. (2) 探索アルゴリズムとは？基本から応用まで分かりやすく解説し .... https://products.sint.co.jp/topsic/blog/search-algorithm. (3) 【探索アルゴリズム】線形探索、二分探索、ハッシュ探索に .... https://breezegroup.co.jp/202006/algorithm-search/. (4) 最良優先探索 - Wikipedia. https://ja.wikipedia.org/wiki/%E6%9C%80%E8%89%AF%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2. (5) サーチ（探索）：アルゴリズムの基本4 - エンジニアの入り口. https://eng-entrance.com/%e3%82%b5%e3%83%bc%e3%83%81%ef%bc%88%e6%8e%a2%e7%b4%a2%ef%bc%89%ef%bc%9a%e3%82%a2%e3%83%ab%e3%82%b4%e3%83%aa%e3%82%ba%e3%83%a0%e3%81%ae%e5%9f%ba%e6%9c%ac4.