순차 탐색

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

이진 탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정
정렬되어 있는 리스트에서만 사용 가능
시간 복잡도는 O(logN)

Tip
이진 탐색의 아이디어는 숫자 맞추기 게임의 승리 전략과 유사하다.
ex.) 상대가 1~10 사이의 숫자 중 하나를 정했을 때 그 숫자가 무엇인지 맞추는 게임을 할 때 가장 일반적인 전략은 범위의 중위값부터 범위를 반씩 좁혀나가면서 비교하는 것이다.

• 재귀 함수를 사용하여 구현한 코드

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)

n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, 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
    
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)
if result == None:
	print('원소가 존재하지 않습니다.')
else:
	print(result + 1)

Python의 이진 탐색 라이브러리

정렬된 배열과 원소를 인자로 받아서 정렬된 배열 안에서 정렬을 유지하며 원소를 삽입할 수 있는 위치(인덱스) 반환(왼쪽부터 or 오른쪽부터)

from bisect import bisect_left, bisect_right

a = [1,2,4,4,8]
x = 4

print(bisect_left(a,x))   # 2
print(bisect_right(a,x))  # 4

• 값이 특정 범위(left~right)에 속하는 데이터 갯수 구하기

def count_by_range(array, left_value, right_value):
	right_index = bisect_right(array, right_value)
	left_index = bisect_left(array, left_value)
	return right_index - left_index

파라메트릭 서치(Parametric Search)

파라메트릭 서치(Parametric Search): 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법
ex.) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결 가능