Binaly Search (二分探索)の理論と実装

コーディング面接の対策の第2回目は、Binaly Search (二分探索)です。

Binaly Search (二分探索)について

Binaly Search (二分探索)とは、ソート済みの配列に対して、任意の値のデータを探索するアルゴリズムです。
1回の処理ごとに配列内の探索する範囲を半分にしていくため、計算量はO(log n)となります。(logの底は2)

Pythonでの実装例

def binary_search(array, query):
    
    def search_query(left, right):
        if right >= left:
            mid = (left + right) // 2
            
            if array[mid] == query:
                return mid

            elif array[mid] > query:
                right = mid - 1
                return search_query(left, right)

            elif array[mid] < query:
                left = mid + 1
                return search_query(left, right)
            
        return "存在しない値です"
    
    return search_query(0, len(array)-1)