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

너무 편향된 알고리즘 문제만 푼 나를 반성하며 이진 탐색에 대하여 정리해보려고 한다.

 

1. 이진 탐색이란?

검색 범위를 줄여나가며 특정 데이터를 검색하는 알고리즘

 

정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다.

리스트 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다.

 

2. 동작 방식

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

1. 배열의 중간 값을 가져온다.
2. 중간 값과 검색 값을 비교한다.
   1. 중간 값이 검색 값과 같으면 종료 (mid = key)
   2. 중간 값이 검색 값보다 크다면 중간 값 기준 오른쪽 구간을 대상으로 탐색 (mid < key)
   3. 중간 값이 검색 값보다 작으면 중간 값 기준 왼쪽 구간을 대상으로 탐색 (mid > key)

 

3. 시간 복잡도

O(logN)

운이 좋다면 찾고자 하는 값이 중간값과 동일하여 탐색이 끝나지만,

최악의 경우에는 남은 데이터가 하나가 될 때 까지 반복한다.

 

전체 데이터 수가 N일때, 첫 번째 탐색 후 에는 N/2

두 번째 탐색에서는 N/2 * 1/2

세 번째 탐색에서는 N/2 * 1/2 * 1/2

K 번째 탐색에서는 ( 1/2 )^K × N 이 된다.

 

최악의 경우에는 남은 자료가 1개가 된다.

(1/2)^K x N = 1을 통해 계산하면

K = log2N 이 나온다.

 

여기서 K의 의미는 시행횟수이다. 즉, 자료의 개수 N에 따른 시행횟수는 log2N이 되고, Big O 표시법으로 O(logN)이 된다.

 

4. 파이썬 구현 코드

1) 반복문 사용

def binary_search(target, data_list) :
    left = 0
    right = len(data_list)-1

    while left <= right :
        mid = (left + right) // 2

        if data_list[mid] == target :   # 중간 값이 검색 값과 같은 경우
            return mid
        elif data_list[mid] < target :  # 중간 값이 검색 값보다 작을 경우
            left = mid + 1
        else :  # 중간 값이 검색 값보다 클 경우
            right = mid - 1
    return 0 # 찾는 값 없음

2) 재귀 사용

def binary_search(target, data_list, left, right) :
    if left > right :   # 찾는 값 없음
        return 1

    mid = (left + right) // 2

    if data_list[mid] == target :   # 중간 값이 검색 값과 같은 경우
        return mid
    elif data_list[mid] < target :  # 중간 값이 검색 값보다 작을 경우
        left = mid + 1
    else :  # 중간 값이 검색 값보다 클 경우
        right = mid - 1
        
    return binary_search(target, data_list, left, right)