[알고리즘] 이진 탐색(Binary Search)

이진 탐색(Binary Search) 이란?

• 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법
• 정렬이 되어있는 배열에서 특정한 값을 찾아내는 알고리즘이다.

https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

 

분할 정복 알고리즘과 이진 탐색

• 분할 정복 알고리즘(Divide and Conquer)
• Divide: 문제를 하나 또는 둘 이상으로 나눈다.
• Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않으면 다시 나눈다.
• 이진 탐색(Binary Search)
• Divide: 리스트를 두 개의 서브 리스트로 나눈다.
• Conquer
• 검색 할 숫자(search) > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
• 검색 할 숫자(search) < 중간값 이면, 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.

 

이진 탐색(Binary Search) 구현

def binary_search(data, search):
    if len(data) == 1 and data[0] == search:
        return True
    if len(data) == 1 and data[0] != search:
        return False
    if len(data) == 0:
        return False
        
    mid = len(data) // 2
    if data[mid] == search:
        return True
    else:
        if data[mid] > search:
            return binary_search(data[:mid], search)
        else:
            return binary_search(data[mid+1:], search)

 

이진 탐색(Binary Search) 시간 복잡도

• n x $\frac{1}{2}$ x $\frac{1}{2}$ x $\frac{1}{2}$... = 1
• n x $\frac{1^k}{2}$ = 1
• n = $2^k$ = $log_2 n$ = $log_2 2^k$
• $log_2 n$ = k
• Big-O 표기법으로는 k + 1이 최종 시간복잡도이고 결국 O($log_2 n$ + 1)이기 때문에 시간 복잡도는 O($log_n$)