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

1. 기본 원리

• (분할) 리스트를 두 개의 서브 리스트로 나눔
• (정복) 검색할 숫자가 중간값보다 크면 뒷 서브 리스트에서 탐색, 반대의 경우에는 앞 서브 리스트에서 탐색

 

2. 생각 정리

• 리스트를 반씩 나누면서 찾고자 하는 포인트와 점점 가까워지게 하는 프로세스를 재귀 용법을 통해 구현

 

3. 코드 구현

• 기존에 정렬되어 있던 리스트에서 특정 값이 있는지 여부를 이진탐색으로 판별하는 코드

def bs(data, s_point):
    print(data)
    medium = len(data) // 2
    if s_point == data[medium]:
        return True
    else:
        if s_point > data[medium]: #중간값보다 찾으려는 값이 클 때
            return bs(data[medium+1:], s_point)
        else: #중간값보다 찾으려는 값이 클 때
            return bs(data[:medium], s_point)

 

4. 시간 복잡도

• 결국 리스트를 반으로 나누는 작업을 리스트 원소 갯수가 1일 때까지 하며 탐색을 하는 방법임
• 그러므로 시간 복잡도는 O(log n)