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

순차 탐색 

리스트 A에 n개의 수가 저장되어 있을 때, 어떤 수 X가 A에 저장되어 있는지 알고 싶다. X가 A에 없는 경우 A의 첫번째 원소부터 마지막 원소까지 모든 수를 살펴봐야 하므로 n번의 비교가 반드시 필요하고, 이에 따른 시간 복잡도는 O(n)이다. 이와 같이 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이 바로 순차 탐색이다.

 

이진 탐색

하지만, 만약 A의 수들이 오름차순으로 정렬된 상태라면 더 적은 비교를 통해 X를 찾을 수 있다. 바로 이진탐색을 이용하는 것이다.  이진 탐색이란 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 탐색 범위가 매우 큰 문제가 주어질 때, 이진 탐색을 이용하면 문제를 효율적으로 해결할 수 있다.

 

시간 복잡도

이진 탐색은 각 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2N에 비례한다. 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개의 원소가 남는다. 동일하게 2단계를 거치면 8개, 3단계를 거치면 4개의 원소가 남는다. 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(log N)을 보장한다.

 

알고리즘 개념 및 구현

이진 탐색은 기본적으로 투포인터 개념을 용용하여 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.

1. 탐색 범위의 시작과 끝을 left, right라는 두 개의 변수(포인터)에 저장한다.

2. left와 right를 더한 뒤 2로 나누고, 이 값을 mid라는 변수에 저장한다(이때, 소수점 이하는 제거한다).

3. 배열에서 mid가 가리키고 있는 원소를 확인한다(array[mid]).

1. mid가 가리키고 있는 원소가 찾고자 하는 수와 같다면 탐색을 종료한다(array[mid] == target)
2. mid가 가리키고 있는 원소가 찾고자 하는 수보다 작다면 탐색 범위를 오른쪽으로 옮긴다(array[mid] < target)
3. mid가 가리키고 있는 원소가 찾고자 하는 수보다 크다면 탐색 범위를 왼쪽으로 옮긴다(array[mid] > target)

4. 3번 과정을 반복한다.

 

https://coderscat.com/binary-search/

재귀 구조나 반복문을 이용하여 아래와 같이 이진 탐색을 구현할 수 있다.

 

재귀 구조

def binary_search(array, target, left, right):
    if left  > right:
        return None
    mid = (left + right) // 2
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array, target, left, mid-1)
    else:
        return binary_search(array, target, mid+1, right)

 

반복문

def binary_search(array, target, left, right):
    while left <= right:
        mid = (left + right) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    return None    

 

파이썬 이진 탐색 라이브러리 

또 파이썬에선 다음과 같은 이진 탐색 라이브러리를 지원한다.

• bisect_left(a, x): 정렬된 순서를 유지하면서 리스트 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
• bisect_right(a, x): 정렬된 순서를 유지하면서 리스트 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

 

이를를 이용해 특정 범위에 속하는 원소의 개수를 쉽게 구할 수 있다.

from bisect import bisect_left, bisect_right

def count_by_range(array, left_value, right_value):
    right_index = bisect_right(array, right_value)
    left_index = bisect_left(array, left_value)
    return right_index - left_index

array = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

# 값이 4인 원소의 개수 출력
print(count_by_range(array, 4, 4)) # 2

# 값이 [-1, 3] 범위에 있는 원소의 개수 출력
print(count_by_range(array, -1, 3)) # 6

 

참고

이것이 취업을 위한 코딩테스트다 with 파이썬

Algorithms in Python(신찬수 저)