이진탐색 - 이분탐색

백준 문제 1920 (수찾기) 문제를 풀다가 이 문제에서 요구하는 알고리즘 개념인 이분탐색에 대해 소개하고자 글을 썻습니다.

 

이분탐색이란?

 

이분 탐색은 분할 정복 기법(devide and conquer)을 응용한 것으로서

배열이 정렬되어 있을 때만 사용이 가능합니다.

 

원리는 간단하게

중간값이 찾는 값보다 적을 때는 더 작은 값으로

중간값이 찾는 값보다 클때는 더 큰값으로 이동하면서 탐색합니다.

 

이진탐색 이용할 시 시간복잡도는 기존 순차 탐색시 시간복잡도 (N)에서 log_2n으로 줄일수 있습니다.

하지만 앞에서 언급했듯이 정렬이 되어 있어야 한다는 단점이 있습니다.

 

이분탐색 동작 방식

 

 

def binary_search (arr, val):
    first, last = 0, len(arr)
    while first <= last:
        mid = (first + last) // 2
        if arr[mid] == val: return mid
        if arr[mid] > val: last = mid - 1
        else: first = mid + 1
    return -1

이분탐색 구현 코드는 위와 같습니다.