[알고리즘] 이진탐색

이진탐색 (Binary Search): 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

분할정복과 이진탐색
1. 분할 정복 (Divide and Conquer)
- Divide: 문제를 하나 또는 둘 이상으로 나눈다.
- Conquer: 나눠진 문제가 충분히 작고 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다.

2. 이진 탐색

• Divide: 리스트를 두 개의 서브 리스트로 나눈다.
• Conquer
  검색할 숫자 > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
  검색할 숫자 < 중간값 이면, 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.
  

코드

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

시간 복잡도

O(logn)