[Algorithm] 이진 탐색 알고리즘

Posted: 2023.05.13 Updated: 2023.05.13

이진 탐색 알고리즘

순차 탐색은 리스트 안의 특정 데이터를 찾기 위해 앞에서 데이터를 하나씩 확인하는 방법이다.

반면 이진 탐색은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.

탐색 방법

이진 탐색

시작점과 끝점, 중간점을 지정한다. (소수점 이하는 제거)

시작점, 끝점 지정

중간 값이 만약 찾고 싶은 값보다 큰 경우 끝 점을 중간 값의 다음 인덱스로 옮긴다. 만약 중간 값이 찾고 싶은 값보다 작을 경우 시작 점을 중간 값의 다음 인덱스로 옮긴다.

중간점이 원하는 값이면 탐색을 종료한다.

시간 복잡도

단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 $log_2N$ 에 비례한다.

시간 복잡도는 $O(logN)$ 을 보장한다.

구현

재귀적 구현

소스코드

def binary_search[array, target, start, end]:
    if start > end:
        return None
    mid = (start + end)
    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 = 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)

출력

10 7
1 3 5 7 9 11 13 15 17 19
4

반복문 구현

소스코드

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end)
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

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)

출력

10 7
1 3 5 7 9 11 13 15 17 19
4

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

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

bisect

소스코드

from bisect import bisect_left, bisect_right

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

print(bisect_left(a, x))
print(bisect_right(a, x))

출력

2
4

위와 같은 로직을 이용하여 특정 범위에 속하는 데이터 개수를 구할 수 있다.

소스코드

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

파라메트릭 서치 (Parametric Search)

특정 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 문제와 같은 최적화 문제를 결정 문제(‘예’ 혹은 ‘아니오’)로 바꾸어 해결하는 기법이다.

일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다.

Better Jeong