[Python] 이진 탐색 (Binary Search)

이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.

정렬된 데이터에서 원하는 데이터를 빠르게 찾을 수 있다는 장점이 있다.

탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다.

 

이진 탐색은 위치를 나타내는 변수 3개를 사용한다.

시작점, 끝점, 중간점이다.

 

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색이다.

 

한번 확인할 때마다 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다.

탐색 범위가 2,000만을 넘어가면 이진 탐색으로 접근하는 것을 고려해보면 좋다.

구현하는 방법에는 두가지가 있다.

 

1. 재귀 함수로 구현

# 이진 탐색 소스코드 구현 (재귀 함수)
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)

2. 반복문으로 구현

# 이진 탐색 소스코드 구현 (반복문)
def binary_search(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(0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

 

bisect 라이브러리 사용법

파이썬에서는 이진 탐색을 쉽게 구현할 수 있도록 bisect 라이브러리를 제공한다.

'정렬된 배열'에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용된다.

 

bisect_left()와 bisect_right() 메소드가 가장 중요하게 사용되며, O(logN)에 동작한다.

- bisect_left() : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메소드

- bisect_right() : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메소드

from bisect import bisect_left, bisect_right

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

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

이를 이용해서 값이 특정 범위에 속하는 원소의 개수를 구하는데 응용할 수 있다. (right - left 이용)

---

본 게시글은 나동빈 저자의 "이것이 코딩테스트다 with 파이썬" 책 내용을 정리한 것입니다.