CodeGym /Javaコース /Python SELF JA /バイナリサーチ

バイナリサーチ

Python SELF JA

レベル 53 , レッスン 1

使用可能

2.1 バイナリサーチの定義とその基本概念

バイナリサーチは、ソートされた配列の中で要素を探すアルゴリズムで、配列を半分に分割するという原則で動作します。このアルゴリズムは、大きな配列に対して線形探索よりも大幅に効率的です。というのも、各イテレーションで配列を2つに分割することで、チェック数を減らしているからです。

基本概念：

ソートされた配列: バイナリサーチはソートされた配列でのみ機能します。
半分に分割: アルゴリズムは探している要素を配列の中央の要素と比較します。
再帰的または反復的分割: 探している要素が中央の要素より小さい場合、検索は配列の左半分で続行され、そうでない場合は右半分で続行されます。
終了条件: 検索は要素が見つかるか、検索範囲が空になると終了します。

重要！バイナリサーチにはソートされた配列が必要です。

バイナリサーチが正しく機能するには、入力データが昇順に並んでいる必要があります。これはアルゴリズムが配列の要素が順序付けられているという事実に依存しているためです。そのため、各検索ステップで要素の半分を効率的に除外することができます。

ソートされた配列の例：


sorted_array = [1, 3, 5, 7, 9, 11, 13]

2.2 バイナリサーチのステップバイステップ実装

バイナリサーチの動作原理:

初期化: 検索の開始境界を設定する（配列の左境界と右境界）。
中央の要素を選択: 配列の中央の要素のインデックスを見つける。
比較: 中央の要素を探している値と比較する。
境界の更新:
1. 中央の要素が探している値と等しい場合、そのインデックスを返す。
2. 探している値が中央の要素より小さい場合、右の境界を更新する。
3. 大きい場合は左の境界を更新する。
繰り返し: 要素が見つかるまで、または左境界が右境界を超えるまで、ステップ2-4を繰り返す。

ステップバイステップのアルゴリズム:

初期化: leftを0に設定し、rightをlen(arr) - 1に設定する。
中央の要素を計算する: mid = (left + right) // 2
目標要素と比較する:
1. もしarr[mid] == targetなら、midを返す。
2. もしarr[mid] < targetなら、left = mid + 1を更新する。
3. もしarr[mid] > targetなら、right = mid - 1を更新する。
繰り返す: left <= rightの間、ステップ2に戻る。
要素が見つからない場合: -1を返す。

Pythonでのバイナリサーチの反復的実装:


def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 使用例:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"エレメント {target} は、インデックス {result} で見つかりました")  # 出力: エレメント 7 は、インデックス 3 で見つかりました

2.3 バイナリサーチの時間計算量 `O(log n)`

バイナリサーチの時間計算量はO(log n)で、nは配列の要素数です。これは、各ステップでアルゴリズムが要素数を半分に分割することを意味し、時間計算量がO(n)の線形探索と比べて探索を大幅に高速化します。

時間計算量の分析:

最良ケース (Best case): 初めのステップで要素が見つかる、O(1)。
平均ケース (Average case): O(log n)。
最悪ケース (Worst case): 最後のステップで要素が見つかるか、要素が存在しない、O(log n)。

時間計算量の分析例:


sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
index = binary_search(sorted_array, target)
print(f"エレメント {target} は、インデックス {index} で見つかりました")  # 出力: エレメント 7 は、インデックス 3 で見つかりました

# アルゴリズムは要素を見つけるために3ステップを実行しました（7個の要素の対数）、 
# これはO(log n)に一致します

計算量の視覚的な表現:

16個の要素からなる配列を考えてみましょう。