이분 탐색 : 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법

선형 탐색은 O(N)에 동작하고, 이분 탐색은 O(log N)에 동작하기 때문에 N의 값이 커질수록 둘의 차이는 커진다.

이분 탐색을 할 때는 st 와 en 변수가 필요합니다. 이 둘은 내가 찾으려고 하는 값의 범위를 나타냅니다.

mid = (st + en)/2 만약 arr[mid]가 찾는 값이면 찾은 것이고

작다면, en = mid -1 크다면, st = mid + 1 로 범위를 재설정 합니다.

또 mid = (st + en)/2 를 반복합니다.

범위 안에 값이 없으면 위 과정을 반복하다가 st 값이 en 값을 역전하게 되는데 이를 범위 안에 값이 없음을 확인하는 결과 입니다. 따라서 반복문에서 조건을 while(st ≤ en) 으로 설정합니다.

func binarysearch(target: Int)->Int{
	var st = 0
	var en = n - 1
	while( st <= en ){
		var mid = (st+en)/2
		if arr[mid] < target {
			st = mid + 1
		}
		else if arr[mid] > target {
			en = mid - 1
		}
		else {
			return 1
		}
				
 	} 
	return 0
}

주의 할점

• 이분탐색을 하고자 한다면 주어진 배열은 정렬되어 있어야 한다.
• 무한 루프에 빠지지 않게 mid 값을 정해야 한다.

위에서 두번째 주의점은 이분탐색을 했을 때 무한 루프에 빠지는 일이 벌어질 때가 있는데

(st 와 en 이 1 차이가 날 때)

이때 mid = (st + en + 1)/2 로 두면 해결될 때가 있다.

parametric search

조건을 만족하는 최소 / 최댓값을 구하는 문제 (최적화 문제)를 결정 문제로 변환해 이분탐색을 수행하는 방법

ex) 랜선 자르기

최적화 문제 - N개를 만들 수 있는 랜선의 최대 길이