🔍 이진 탐색 (Binary Search)

• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법인 순차 탐색(Sequential Search)과 달리,
• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.
• 즉, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색 과정이다.
• 이진 탐색은 배열 내부의 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다.

이진 탐색 동작 예시

이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는다고 가정해보자.

STEP 1

• 시작점과 끝점을 확인한 다음 둘 사이에 중간점을 정한다.
• 중간점이 실수일 때는 소수점 이하를 버린다.
  • 그림에서 각각의 인덱스는 시작점은 [0], 끝점은 [9], 중간점은 (4.5에서 소수점 이하를 버려서) [4]이다.
• 다음으로 중간점 [4]의 데이터 8과 찾으려는 데이터 4를 비교한다.
• 중간점의 데이터 8이 더 크므로 중간점 이후의 값은 확인할 필요가 없다.
  • 끝점을 [4]의 이전인 [3]으로 옮긴다.

STEP 2

• 시작점은 [0], 끝점은 [3], 중간점은 (1.5에서 소수점 이하를 버려서) [1]이다.
• 중간점이 위치한 데이터 2는 찾으려는 데이터 4보다 작으므로 이번에는 값이 2 이하인 데이터는 더이상 확인할 필요가 없다.
  • 시작점을 [2]로 변경한다.

STEP 3

• 시작점은 [2], 끝점은 [3]이다.
• 이때 중간점은 (2.5에서 소수점 이하를 버려서) [2] 이다.
• 중간점에 위치한 데이터 4는 찾으려는 데이터 4와 동일하므로 탐색을 종료한다.
  

정리

• 전체 데이터 개수는 10개이지만, 이진 탐색을 통해 총 3번의 탐색으로 원소를 찾을 수 있었다.
• 이진 탐색은 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다.

📝 이진 탐색 구현하기

• 이진 탐색을 구현하는 방법에는 2가지가 있는데, 하나는 재귀함수를 이용하는 방법이고, 다른 하나는 단순하게 반복문을 이용하는 방법이다.
• 찾고자 하는 요소의 위치를 출력하는 이진 탐색 함수를 구현해보자.

재귀함수로 구현하기

# 이진 탐색 소스코드 구현 (재귀 함수)
def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
        return binary_search(array, target, mid + 1, end)

# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

반복문으로 구현하기

# 이진 탐색 소스코드 구현 (반복문)
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid - 1
        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
            start = mid + 1
    return None

# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

💫 bisect 라이브러리를 사용한 이진 탐색

• 파이썬에서는 이진 탐색을 쉽게 구현할 수 있도록 bisect 라이브러리를 제공한다.
• bisect 라이브러리는 '정렬된 배열'에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용된다.
• bisect 라이브러리에서는 bisect_left() 함수와 bisect_right() 함수가 가장 중요하게 사용되며, 이 두 함수는 시간복잠도 O(logN)에 동작한다.
  • bisect_left(a, x) : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
  • bisect_right(a, x) : 정렬된 순서를 유지하도록 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드

예시

• 정렬된 리스트 [1, 2, 4, 4, 8]이 있을 때, 새롭게 데이터 4를 삽입하려 한다고 가정해보자.
• 이때 bisect_left(a, 4)와 bisect_right(a, 4)는 각각 인덱스 값으로 2와 4를 반환한다.

• 소스코드로 구현하면 다음과 같다.

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x))  # 2
print(bisect_right(a, x))  # 4

특정 범위에 속하는 원소 개수 구하기

• bisect_left() 함수와 bisect_right() 함수는 정렬된 리스트에서 값이 특정 범위에 속하는 원소의 개수를 구하고자 할 때, 효과적으로 사용될 수 있다.

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index

# 리스트 선언
a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

# 값이 4인 데이터 개수 출력
print(count_by_range(a, 4, 4))  # 2

# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(a, -1, 3))  # 6

• 위 코드에서 count_by_range(a, left_value, right_value)함수는 정렬된 리스트에서 값이 [left_index, right_index]에 속하는 데이터의 개수를 반환한다.
  • 다시 말해, left_index <= x <= right_index인 원소의 개수를 O(logN)으로 빠르게 계산할 수 있다.

📍 References

• 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저
• https://youtu.be/94RC-DsGMLo