[アルゴリズム基本]二分探索アルゴリズム

4754 ワード
アルゴリズムベース テキストリンク

にぶんたんさく


これは、
  • 昇順テーブルで特定の値の位置を検索するアルゴリズムです.
  • この探索者は「二つに分ける」という意味だ.検索する資料を2つに分けて、検索値がある可能性のある場所だけを検索します.
    • 欠点は、
  • の検索原理でソートされたリストでしか使用できないことです.
  • ですが、検索を繰り返すたびに目標値が見つかる確率が目標値の2倍になるので、速度が速いです.

    • 展開

  • を並べます.
  • の中間位置が見つかりました.
  • で見つかった値と中間位置の値を比較します.
  • なら欲しい値が見つかったので、位置番号を結リンゴ値に戻します.
  • で検索された値が中間位置値より大きい場合、中間位置の右側の配列についてナビゲートを再開します.(第1のプロセスから繰り返す)
  • で検索された値が中間位置値より小さい場合、中間位置の左側の配列についてナビゲートを再開します.(第1のプロセスから繰り返す)

    • 画像ソース

    時間の複雑さ

  • 分探索1つの値を比較するごとに,探索値の範囲を半分に縮小する.
  • には,時間的複雑度がO(logN{logN}logN)の半分に縮小するプロセスがある.

    • インプリメンテーションコード

    def binary_search(numbers, target):
    """
    이분 탐색 알고리즘으로 특정 값을 찾는다.
    값이 있으면 값의 인덱스를 반환하고,
    값이 없으면 -1를 반환한다.
    """

    left = 0
    right = len(numbers) - 1

    while left <= right:
        mid = (left + right) // 2

        if target == numbers[mid]:
            return mid

        elif target > numbers[mid]:
            left = mid + 1

        else:
            right = mid - 1

    return -1


if __name__ == '__main__':
    numbers = [6, 5, 6, 4, 3, 2, 1]
    target = 3

    numbers.sort()
    target_idx = binary_search(numbers, target)

    print(numbers)
    print(target_idx)

'''
출력 결과

[1, 2, 3, 4, 5, 6, 6]
2
'''

    Ref

  • みんなのアルゴリズムとPython-李勝燦
    • CSSボックスモデル、MediaQuery、Grid
    [React] props & component