[C++] 이분 탐색

안녕하세요! 테크지니어22입니다.

오늘은 이분 탐색에 대해서 알아보도록 하겠습니다.

 

1. 이분탐색이란?

정렬되어 있는 배열에서 특정 데이터를 찾기 위해 탐색 범위를 절반으로 줄여가며 찾는 탐색법입니다.

일반적으로 선형탐색 시간초과가 발생하면 이분탐색을 떠올리게 됩니다.

하지만 이분 탐색이 가장 많이 사용하는 상황은 최적화문제를 결정 문제로 변환이 필요할 때입니다.

'한쪽 구간은 뭔가가 되고, 한쪽 구간은 안 된다. 따라서 어떤 한 값의 가능 여부를 알면 그 값을 기준으로 어떤 구간을 탐색할지 결정할 수 있다' 가 핵심입니다.

 

2. 탐색구간

- 어떤 탐색구간을 사용하건 구현상의 선택의 문제이기 때문에 자신에게 편한 것을 선택하면 됩니다.

 

[lo,hi] 구간

• 조건: while (lo ≤ hi)
• 경계 업데이트 : if(condition) { lo = mid + 1 ;} else { hi = mid - 1 ;}

[lo,hi) 구간

• 조건: while (lo < hi)
• 경계 업데이트: if(condition) {lo = mid + 1 ;} else {hi = mid ; }

(lo,hi] 구간

• 조건: while (lo < hi)
• mid = left + ( right-left +1 ) / 2
• 경계 업데이트: if(condition) {lo = mid ;} else {hi = mid-1 ; }

(lo,hi) 구간

• 조건: while (lo + 1 < hi)
• 경계 업데이트 : if(condition) { lo = mid ;} else { hi = mid ;}
• 열린 구간이므로 구간 설정 조심 → [lo+1, hi-1]과 같기 때문.

 

 

3. 코드

순수 구현

저는 (lo,hi)로 탐색 구간을 설정하고 이를 기반으로 구현하였습니다.

 

BinarySearch

int BinarySearch(int lo, int hi, int target){

	while(lo + 1 < hi){
		int mid = (lo+hi)/2 ;
		
		if(arr[mid] <= target)
				lo = mid;
		else hi = mid	
	}
	return lo
}

 

lower_bound, upper_bound

// v[mid] >= target 인 경우 정답은 hi에 있음.
// v[mid] <= target인 경우 정답은 lo에 있음.
int lowerBound(int size , int target){
	int lo = -1 ; int hi = size
	while(lo+1 <hi) {
		int mid = (lo + hi ) / 2; 
		if(a[mid] >= target) hi = mid;
		else lo = mid ;
	}
	return hi ;
}


int upperBound(int size ,int target) {
	int lo = -1 ; int hi = size;
while(lo+1 <hi) {
		int mid = (lo + hi ) / 2; 
		if(a[mid] > target) hi = mid;
		else lo = mid ;
	}
	return hi ;
}

 

 

STL

binary_search(v.begin(), v.end(), 찾을값)

- true 또는 false를 반환

 

upper_bound (v.begin(), v.end(), 찾을값)

- 못 찾으면 두번째인자 반환

- 찾을 값이 담긴 마지막 요소의 다음 주소를 반환

 

lower_bound (v.begin(), v.end(), 찾을값)

- 못 찾으면 두번째인자 반환

- 찾을 값이 담긴 첫번째 요

 

 

4. 중간 값을 구하는 방식

a. int mid = low + (high - low) / 2

- low + high 값이 범위를 넘어서는 경우일 때 사용.

 

b. int mid = (low + high) / 2

5. 추가 내용

파라메트릭 서치 전략

1. 오름차순 정렬하기
2. check 함수 만들기
3. lo, hi 설정
4. check(lo), check(hi) 확인. 둘은 무조건 달라야 함.
5. 문제가 check(lo)값의 가장 큰 값을 요구하면 답은 lo에, 문제가 check(hi)값의 가장 작은 값은 요구하면 답은 hi에 있다.
6. 5를 토대로 lo,hi를 재설정한다. ( min ≤ target ≤ max, lo+1 == h )
   - 답이 되는 lo는 lo = min, hi = max+1
   답이되는 hi는 lo = min -1 , hi = max

 

6. 참고자료

- https://techgineer22.tistory.com/1

[백준/C++] 알고리즘 3151번 - 합이 0

- https://techgineer22.tistory.com/2

[백준/C++] 알고리즘 2467번 - 용액

- https://techgineer22.tistory.com/3

[백준/C++] 알고리즘 18869번 - 멀티버스 II

- https://techgineer22.tistory.com/4

[백준/C++] 알고리즘 2805번 - 나무 자르기

-