• 정렬된 배열에서 특정 값을 빠르게 찾기 위한 알고리즘
• 시간복잡도 : O(logN)

개념 & 기본 흐름

개념

• 전제 조건 : 배열이 정렬되어 있을 것
• 방식 : 중간 값을 기준으로 탐색 범위를 절반으로 줄여나감

기본 흐름

1. start = 0, end = 배열길이 - 1, mid = [(start + end) // 2]
2. 중간값(arr[mid])과 찾고자 하는 값(target)을 비교:
   1. arr[mid] == target : 찾음
   2. arr[mid] < target : 오른쪽 구간 탐색(start = mid + 1)
   3. arr[mid] > target : 왼쪽 구간 탐색 (end = mid - 1)

핵심 소스코드

반복문

# 전제조건 : 정렬된 배열
def binary_search(arr, target):
	start, end = 0, (len(arr) -1)
	
	while start <= end:
		mid = (start + end) // 2
		
		if arr[mid] == target:
			return arr[mid]
		elif arr[mid] > target:
			end = mid - 1
		else:
			start = mid + 1
	
	return -1 # 못 찾은 경우

재귀

def recursive_binary_search(arr, target, start, end):
	if start > end:
		return -1 # 못 찾은 경우
	
	mid = (start + end) // 2
	mid_value = arr[mid]

	if mid_value == target:
		return mid_value
	
	if mid_value > target:
		return recursive_binary_search(arr, target, start, mid - 1)
	else:
		return recursive_binary_search(arr, target, mid + 1)

이분탐색 개념을 응용한 함수

lower_bound 함수

a = [1, 2, 4, 4, 4, 7, 9]
target = 4

# target보다 크거나 같은 값이 처음 등장하는 인덱스를 찾는 함수
def lower_bound(arr, target):
	left, right = 0, len(arr) - 1
	
	while left < right:
		mid = (left + right) // 2
		
		# 목적 : arr[i] >= target이 처음으로 참이 되는 i 찾기
		if arr[mid] < target:
			# 이 경우에는 중앙값이 정답이 아니므로 left = mid+1
			left = mid + 1
		else:
			# arr[mid] > target 경우 : mid값이 답일 수도 있으므로 right = mid(mid - 1 아님)
			right = mid
			
	return left

upper_bound 함수