[알고리즘/Algorithm] 파이썬으로 이진 탐색 (Binary Search) 알아보기

이진 탐색(Binary Search)이란

• 정렬된(중요!!) 자료(리스트)를 반으로 나누어 가며 데이터를 탐색하는 방법

 

이진 탐색 흐름

ex) 위 그림과 같이 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 리스트에서 숫자 8을 찾는다!

1. 리스트의 중간에 위치한 데이터(이하 피벗/pivot)를 확인한다. 여기서는 6
2. 해당 피벗에 데이터(6)를 확인하고, 3가지 경우로 나뉜다.
   1. 해당 피벗 데이터가 찾는 데이터면 True를 리턴
   2. 찾는 데이터가 피벗 보다 작으면 피벗 기준 왼쪽 값들을 기준으로 재 탐색
   3. 찾는 데이터가 피벗 보다 크면 피벗 기준 오른쪽 값들을 기준으로 재 탐색
3. 데이터를 찾을 때까지, 혹은 데이터의 개수가 1이 될 때까지 1번과 2번을 반복한다.

 

파이썬을 통해 구현한 이진 탐색

def binary_search(data, search):
    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

    mid = len(data) // 2
    if search == data[mid]:
        return True
    else:
        if search > data[mid]:
            return binary_search(data[mid:], search)
        else:
            return binary_search(data[:mid], search)

재귀 함수를 통해 이진 탐색을 구현했다.

 

재귀 함수는 베이스 구문(재귀 탈출 구문)이 없으면 무한히 반복돼 스택오버 플로우 에러를 유발하기 때문에,

위와 같이

데이터를 찾으면 True를 리턴 하는 if문과,

데이터를 찾지 못하면 False를 리턴 하는 if문,

그외 예외 처리로 베이스 구문을 만들어 주었고.

 

그 아래 코드부터 본격적인 이진 탐색 로직이 구현돼 있다.

피벗(변수 mid)을 기준으로 

만약 그 피벗에 데이터가 찾는 데이터면 바로 if문을 거쳐 True를 리턴하고,

그렇지 않으면 위 이진 탐색 흐름에서 설명한 2-2, 2-3 로직을 반복하며 해당 데이터를 찾게 구현해줬다.