[WEEK02] 이분 탐색

이분 탐색

이분 탐색

이분 탐색(이진 탐색)은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이분 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 logN에 비례한다.

구현

• 배열을 정렬한다.
• 정렬된 배열에서 왼쪽 끝 인덱스 left와 오른쪽 끝 인덱스 right을 이용해 중간 인덱스 mid 값을 찾는다.
• mid 인덱스와 배열에서 찾고자 하는 값 target을 비교한다.
• target이 나올 때까지 탐색 과정을 반복한다.
  - mid 값보다 target이 크다면 left를 mid+1로 이동시켜, 오른쪽 구간에서 탐색한다.
  - mid 값보다 target이 작다면 right을 mid-1로 이동시켜, 왼쪽 구간에서 탐색한다.
• target이 없다면, None을 반환한다.

이분 탐색 구현

def binary_search(array, target):
    array.sort() # 정렬
    
    left = 0
    right = len(array)-1
    
    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를 삽입할 가장 오른쪽 인덱스 반환

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))

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

이분 탐색 관련 백준 문제 Github 링크
백준 이분 탐색 관련 문제