二分探索

二分探索（Binary Search）の説明：

二分探索は、 ソート済みの配列から特定の要素を効率的に探索するためのアルゴリズムです[1-3].

探索方法 [1, 3]:

1. 配列の中央の要素を調べます。

2. 探索したい値と中央の要素を比較します。

3. もし探索したい値が中央の要素と一致する場合、探索は成功です。

4. もし探索したい値が中央の要素より小さい場合、配列の前半部分に対して二分探索を繰り返します。

5. もし探索したい値が中央の要素より大きい場合、配列の後半部分に対して二分探索を繰り返します。

6. 探索範囲がなくなるまで、上記の手順を繰り返します。

計算量:

• 時間計算量： O(log n) [1, 4]

図による説明:

例えば、以下のソート済みの配列から key = 31 を二分探索で探す場合 [5]:

A[] = {10, 20, 31, 40, 50, 60, 70}

1. 初期状態: l = 0, r = n

2. 中央のインデックス m = (l + r) / 2 を計算します。

3. A[m] と key を比較します。

注意点:

• 二分探索は、配列がソート済みであることが前提条件です。

• 配列がソートされていない場合、事前にソートを行う必要があります。