이진 탐색 Bineary Search (개념)

다히·2023년 2월 3일

algorithm bisect 이진탐색 파라메트릭 서치

Algorithm

목록 보기

7/8

순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인하는 방법

이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

시작점, 끝점, 중간점을 이용해 탐색 범위 설정
시간 복잡도 $\rm{O(logN)}$ 을 보장하므로, 큰 수를 보면 가장 먼저 이진 탐색을 떠올릴 수 있어야 함

동작 예시

리스트: 0 2 4 6 8 10 12 14 16 18
찾으려는 데이터: 4

1) 시작, 끝, 중간점 설정

중간점은 소수점 이하 제거해서 사용

2) 찾고자 하는 값과 중간점의 값을 비교해서, 찾아야 하는 탐색 범위를 줄일 수 있음

4가 중간점의 값 8보다 작으므로 중간점보다 왼쪽에 있는 데이터에 대해서만 탐색하면 되고, 이때 끝점은 중간점보다 하나 앞에 있는 값, 중간점은 다시 시작점과 끝점의 중간 지점으로 재설정됨

3) 같은 방식으로 탐색 범위 및 시작, 끝, 중간점 재설정

4) 중간점의 값과 찾고자 하는 값이 같아지면 탐색 종료

시간 복잡도

단계마다 탐색 범위를 2로 나누는 것과 동일하므로, 연산 횟수는 $\rm{log_2 N}$ 에 비례

ex) 이상적인 경우, 초기 데이터 32개 → 1단계 후: 16개 → 2단계 후: 8개 → 3단계 후: 4개

즉, 이진 탐색은 탐색 범위를 줄이며, 시간 복잡도는 $\rm{O(logN)}$ 을 보장

소스코드: 재귀적 구현

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)
# __main__
n, target =  10, 7
a = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
result = binary_search(a, 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

이진 탐색 라이브러리

표준 라이브러리 bisect 이용

from bisect import bisect_left, bisect_right

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

값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right

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

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