2 つのパーティション

意味

二分法は、要素の順序付きリストを入力とするアルゴリズムです。

検索対象の要素がリストに含まれている場合、二分検索はその位置を返し、それ以外の場合は null を返します。

基本的な考え方

1. この方法はデータ量が多い場合に適しています。
2. 二分検索を使用する場合は、データを並べ替える必要があります
3. データが昇順で並べ替えられていると仮定すると、特定の値キーについて、比較はシーケンスの中間位置から開始されます。
4. 現在位置の arr[mid] 値が key と等しい場合、検索は成功します。
5. key が現在の位置の値 arr[mid] より小さい場合、シーケンスの前半で arr[low,mid-1] を検索します。
6. key が現在の位置の値 arr[mid] より大きい場合は、シーケンスの後半で arr[mid+1,high] が見つかるまで検索を続けます。

時間の複雑さ: