• 순차 탐색 : 데이터를 찾기위해 앞에서부터 데이터를 하나씩 확인
• 이진 탐색 : 정렬되어있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
  • 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.

이진 탐색

• 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 logN에 비례한다.
• 탐색 범위를 절반씩 줄이면서 시간 복잡도 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)
        
...

result = binary_search(array, target, 0, n - 1)
if result == None:
	print("Not Exist")
else:
	print(result + 1)

이진 탐색 라이브러리

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

from bisect import bisect_left, bisect_right

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

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

Example

• 떡볶이 떡 만들기
• 설정 높이가 커질 수록 잘린 떡의 길이는 줄어들고, 작아질 수록 떡의 길이는 늘어날 것이다.
• 현재 이 높이로 자르면 조건을 만족할 수 있는가 ? 를 확인하여 조건만족 여부 (Yes or No)에 따라 탐색 범위를 좁혀 해결할 수 있다.
  • 절단기 높이가 10억까지 정수 중 하나인데, 이렇게 큰 탐색범위의 경우 먼저 이진 탐색을 떠올려야한다.

...

start = 0
n = max(array)

result = 0
while (start <= end):
	total = 0
    mid = (start, end) // 2
    for x in array:
    	if x > mid:
        	total += x - mid
            
	if total < m:
    	end = mid - 1
    else:
    	result = mid
        start = mid + 1
        
print(result)

정렬된 배열에서 특정 수의 개수 구하기

• 시간복잡도 O(logN) 알고리즘을 요구하는 것이 핵심
• 선형탐색으로는 시간초과 판정
  • 데이터가 정렬되어있으므로 이진 탐색을 수행 !
• 특정 값이 특장하는 첫 번째 위치와 마지막 위치를 찾아 위치 차이를 계산해 문제를 해결할 수 있다.
• bisect_left, bisect_right 이용하는 문제