[algo]バイナリ探索とは?

バイナリナビゲーション

整列した配列でデータを検索しようとすると、検索方法は検索範囲を半分に縮小します.
2点検索(バイナリ検索/バイナリ検索)の基本条件は、次のとおりです.
エレメントは、昇順または降順で配列されたアレイで使用できます.

バイナリナビゲーションの時間的複雑さとbigoタグ

O(logN)N個のサイズの配列に移動すると、その配列はN、N/2、N/4、N/8、...および1で実行されます.ここで実行されるナビゲーション回数が時間的複雑度であり、その値がKである場合.
1に2を乗じてKに等しいとしたら?Nになる.
2^K = N
K = log2N
すなわち,バイナリプローブの時間的複雑度はO(logN)である.

実装の準備

target:検索する値
data:昇順(降順)で並べ替えたlist
start:データの初期値インデックス(インデックスがキー)
end:dataの前の値インデックス
mid:start,endの中間インデックス

実装の概要

データの中間値が検索する値であるかどうかを確認します(mid)
そうでない場合は、start、end値を移動するためにサイズ関係を比較します.
同じ演算を繰り返す(再帰的に実現可能)

コードで表す

dataからtargetを検索し、正しい場合はindex値を返します.
ない場合はNoneに戻ります

1. while start <= end:

# 바이너리 서치
# data 중에서 target 을 검색하여 index 값을 return 한다.
# 없으면 None을 return한다.

def binary_search(target, data):
    data.sort()
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return mid # 함수를 끝내버린다 // 타겟이 있으면 인덱스 리턴
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return None # 타겟이 없으면 while문을 빠져 나오므로 None을 리턴

# 테스트용 코드
if __name__ == "__main__":
  li = [i**2 for i in range(11)]
  target = 9
  idx = binary_search(target, li)

  if idx:
      print(li[idx])
  else:
      print("찾으시는 타겟 {}가 없습니다".format(target))

2.再帰的実現

# data는 오름차순으로 정렬된 리스트
def binary_search_recursion(target, start, end, data):
    if start > end:  # 타겟이 없으면 None을 리턴 (재귀 종료 조건)
        return None 

    mid = (start + end) // 2

    if data[mid] == target:
        return mid # 타겟이 있으면 인덱스 리턴
    elif data[mid] > target:
        end = mid - 1
    else:
        start = mid + 1        

    return binary_search_recursion(target, start, end, data) # 함수 내에서 start, end 조정해준 다음 해당 값을 똑같이 호출해줌

# 테스트용 코드
if __name__ == '__main__':
    li = [i*3 for i in range(11)]
    target = 6
    idx = binary_search_recursion(target, 0, 10, li)

    print(li)
    print(idx)

Sources

https://wayhome25.github.io/cs/2017/04/15/cs-16/
https://cjh5414.github.io/binary-search/