二分探索(Binary Search)

探索基本

二分探索とは

二分探索とは、ソート済みである配列の中から、目的の値が存在するかを調べる探索アルゴリズムです。高速でわかりやすいため非常に良く使われます。

線形探索はソートしていない配列でも探索することができました。二分探索は、配列がソート済みであるという条件があるものの、線形探索よりも高速に探索することができます。

2分探索の計算量は\(O(logn)\)なので、線形探索の計算量\(O(n)\)に比べて非常に高速です。

例えば、辞書などの検索などでも用いられます。
調べたい単語が「linear」だったとしましょう。適当に開いたページに「search」という単語があったとしたら、「L」は「S」よりも前にあるはずです。つまり、「search」の右半分を無視して、左半分だけを調べるだけで済むのです。
これを繰り返していくと、前から一つずつ単語を見て「linear」を探すよりも、効率的に探索することができます。

アルゴリズム

ソート済み配列内のどこにxが存在するか、を調べる時に用いられます。配列は昇順(小さいものが先頭)にソートされているものとします。

  1. xと配列の中間にある要素を比べて、大小関係を調べる
  2. xと等しければ、中間にあった要素のindexを出力して終了する
  3. xの方が大きければ、右側半分にある部分配列に対して1と2の探索を行う
  4. xの方が小さければ、左側半分にある部分配列に対して1と2の探索を行う

計算量

配列の長さがnだとすると、一度中間を調べるごとに調べるべき配列が半分になるので、平均と最悪の計算量は\(O(logn)\)になります。

はじめに目的の値が見つかるときを考えると、最善の計算量は\(O(1)\)になります。

計算量の証明について(上級者向け)

配列の長さをn、またcを定数として、二分探索の計算量は、

$$T(n) = T(n/2) + c$$

で表すことができます。ここから、マスター定理やRecursion Tree Method などを用いることで先程の計算量を見積もることができます。

プログラム例

Pythonでの例 (Colaboratory などで確認してみて下さい)

def binary_search(arr,x): 
  #l,rはどこからどこまでの配列を調べるかを与えます
  l = 0
  r = len(arr) - 1
  while l <= r:
    mid = l + (r-l)//2
    if x == arr[mid]:  # xがちょうど中間にあったとき
      return mid
    elif x < arr[mid]: # xが左側の配列にあるとき
      r = mid - 1
    else:              # xが右側の配列にあるとき
      l = mid + 1
  return -1
arr = [1,4,5,8,10,24,55,66,190]
print(binary_search(arr,55))   # 出力は6
print(binary_search(arr,4))    # 出力は1
print(binary_search(arr,1000)) # 出力は-1

C++での例

#include <bits/stdc++.h>
using namespace std;
int binary_search(int arr[], int arr_len, int x) {
    int l = 0;
    int r = arr_len - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (x == arr[mid]) {
            return mid;
        } else if (x < arr[mid]) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return -1;
}
int main() {
    int arr[] = {1, 4, 5, 8, 10, 24, 55, 66, 190};
    int arr_len = sizeof(arr) / sizeof(arr[0]);
    cout << binary_search(arr, arr_len, 55) << endl;
    cout << binary_search(arr, arr_len, 4) << endl;
    cout << binary_search(arr, arr_len, 1000) << endl;
    return 0;
}

関連問題

ABC119 D – Lazy Faith:二分探索を上手く用いないと計算に時間がかかりすぎてしまう問題。

探索基本

Posted by cs-learner