[탐색과 정렬] 이분 탐색

이분 탐색(Binary search)

이분(二分)이란 둘로 나눈다는 뜻으로, 탐색할 자료를 둘로 나누어 찾는 값이 있을 법한 곳을 탐색한다.

이미 정렬되어 있는 자료에서 탐색 범위를 줄여가며 찾고자 않는 값을 찾는 탐색 방법이다.

이진 탐색이라고도 부른다.

이미지 출처 : https://velog.io/@ming/%EC%9D%B4%EB%B6%84%ED%83%90%EC%83%89Binary-Search

계산 복잡도는 \(\mbox{O}(\log{n})\)

이분 탐색을 하기 위해서는 자료가 정렬되어 있어야 하지만, 필요한 값을 여러 번 찾아야 한다면 자료를 한 번 정렬한 후 이분 탐색을 이용하는 것이 효율적이다.

 

 

코드

def binary_search(val, list):
    start = 0
    end = len(list) - 1

    while start <= end:
        mid = (start + end) // 2
        if val == list[mid]:
            return mid
        elif val < list[mid]:
            end = mid - 1
        else:
            start = mid + 1
    return -1