이분 탐색(Binary Search)이란?

이분 탐색이란 데이터가 정렬되어 있는 배열에서 특정한 값(X)을 찾는 알고리즘을 의미한다. X를 찾는 과정은 다음과 같다.

우선, 배열의 중간 값을 X와 비교한다. X가 해당 중간 값보다 작으면 탐색의 대상이 되는 배열을 중간 값 기준 좌측의 데이터로,

중간 값보다 크면 우측의 데이터로 조정한다. X를 찾을 때까지 이 과정을 반복한다. 이분 탐색의 시간 복잡도는 O(logN)이다.

 

### 직접 구현 ###
def binary_search(target, A, left, right):
    if left > right:
        return False
    mid = (left + right) // 2
    if target == A[mid]:
        return True
    elif target < A[mid]:
        return binary_search(target, A, left, mid-1)
    else:
        return binary_search(target, A, mid+1, right)



### Python 내장 함수(bisect) ###
from bisect import bisect_left, bisect_right 
# bisect_left(literable, value) : 왼쪽 인덱스를 구하기
# bisect_right(literable, value) : 오른쪽 인덱스를 구하기

nums = [0,1,2,3,4,5,6,7,8,9] 
n = 5 

print(bisect_left(nums, n))  # 5
print(bisect_right(nums, n)) # 6


## 응용 문제 : 5 ~ 7 을 갖는 요소의 개수 구하기 ##
def cal_counts(nums, left_value, right_value): 
		right_index = bisect_right(nums, right_value) 
		left_index = bisect_left(nums, left_value) 
		return right_index - left_index 


nums = [-1, -3, 5, 5, 4, 7, 1, 7, 2, 5, 6] 
nums.sort() # 이분 탐색 전 정렬은 필수 
 
print(cal_counts(nums, 5, 7)) # 요소의 개수는 : 6

 

▶ 관련 링크

2021.11.17 - [알고리즘] - 이분 탐색(Binary Search)이란?

2021.11.17 - [알고리즘] - 이분 탐색 : 수 찾기(백준 1920번)

2021.11.17 - [알고리즘] - 이분 탐색 : 공유기 설치(백준 2110번)

2021.11.17 - [알고리즘] - 이분 탐색 : 나무 자르기(백준 2805번)

2021.11.17 - [알고리즘] - 이분 탐색 : 가장 긴 증가하는 부분 수열(백준 11053번)

2021.11.17 - [알고리즘] - 이분 탐색 : 두 용액(백준 2470번)

2021.11.17 - [알고리즘] - 이분 탐색 : 사냥꾼(백준 8983번)