Binary Search 이분 탐색

Binary Search (이분 탐색)

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 O(logN) 알고리즘

정렬된 리스트에서 탐색 범위를 계속 반으로 줄여나가기에 효율이 좋다.

중간값 mid(low+high의 반값)를 선택하고, 찾고자 하는 값 value와 비교하여 value보다 list의 인덱스 mid값이 크다면 mid를 작은쪽으로 반으로 줄인 후 다시 Search, 그 반대의 경우 큰쪽으로 반으로 줄인다.

검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

 

<파이썬 구현>

array - sorting된 리스트

value- 찾고자 하는 값

def binarySearch(array, value, low, high):
    if low > high:
            return False
        mid = (low+high) // 2
        if array[mid] > value:
            return binarySearch(array, value, low, mid-1)
        elif array[mid] < value:
            return binarySearch(array, value, mid+1, high)
        else:
            return mid

 

시간 복잡도

 

*관련 백준 문제 링크

www.acmicpc.net/problem/1920

 

*시간 복잡도 참고 link

https://jwoop.tistory.com/9