[알고리즘] 이분탐색(Binary Search)

탐색

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

이분탐색

• 단게마다 탐색 범위를 2로 나누느것과 동일
• 연산 횟수 : log2N에 비례
  ex) 초기 데이터 개수가 32일때 이상적으로 1단계를 거치면 16개 가량의 데이터만 남음 다음 8개, 그 다음 4개…
• 탐색범위를 절반씩 줄이며, 시간복잡도 O(logN)을 보장

파라메트릭 서치(Parametric Search)

• 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법
• ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
• 일반적으로 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있음

코드

int left = 0;
int right = 100000;
int mid = (left + right) / 2;

while (left <= right) {
	mid = (left + right) / 2;
    
    if(mid == answer)
    	return mid;
        
	if (answer > mid)
		right = mid - 1;
	else 
		left = mid + 1;
}