<모든 코드는 C++를 기반으로 작성되었습니다.>

Chapter 7 :: 이진 탐색

예제 1. 부품 찾기

• 매장에 부품은 최대 백만개 있을 수 있고 찾을 부품도 최대 백만개 있을 수 있기 때문에 생각없이 찾으려하면 100만 X 100만번 연산해야한다.
• 당연히 그렇게 푸는게 아니고 $O(log(n))$ 시간복잡도를 가지는 이진 탐색 알고리즘을 사용해야 한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

static int N, M;
static vector<int> vecN, vecM;

bool binarySearch(int key) {
	int start = 0, end = vecN.size() - 1;
	while (start <= end) {
		int mid = (start + end) / 2;
		if (key == vecN[mid]) return true;
		else if (key < vecN[mid]) end = mid - 1;
		else start = mid + 1;
	}
	return false;
}

int main() {
	cin >> N;
	vecN = vector<int>(N);
	for (int i = 0; i < N; ++i) cin >> vecN[i];
	cin >> M;
	vecM = vector<int>(M);
	for (int i = 0; i < M; ++i) cin >> vecM[i];

	sort(begin(vecN), end(vecN));	// 중요! 이진탐색 전 정렬 필수!

	for (int i = 0; i < M; ++i) {
		if (binarySearch(vecM[i])) cout << "YES ";
		else cout << "NO ";
	} cout << '\n';
}

• 이진 탐색 전에 꼭 정렬해야한다는 것을 꼭 기억하자!
  

예제 2. 떡볶이 떡 만들기

너무 중요한 문제이므로 문제도 함께 첨부한다.

오늘은 떡볶이 떡을 만드는 날이다. 떡의 길이는 일정하지 않으므로 절단기에 높이(H)를 지정하고 잘라서 맞추려고 한다. 이때 자르고 남는 길이는 손님에게 주려고 한다.
예를 들어, 높이가 19, 14, 10, 17cm인 떡이 있고, 절단기 높이를 15cm로 가정하면 자르고 남는 떡의 길이는 4, 0, 0, 2cm이고 총 6cm이다. 손님은 6cm를 가져간다.
이때, 손님이 요청한 길이가 M일 때 적어도 M 만큼의 떡을 얻기 위해 절단기에 설정해야 하는 높이 H의 최댓값을 구하는 프로그램을 작성하시오.
($1 \leq N \leq 1,000,000, 1 \leq M \leq 2,000,000,000, 1 \leq H \leq 1,000,000,000$ )

예제

<입력>
4 6
19 15 10 17
<출력>
15

• 파라매트릭 서치 Parametric Search란, 최적화 문제를 결정 문제로 바꿔 해결하는 기법을 말한다.
• '범위 내에서 조건을 만족하는 가장 큰 값을 찾는 것'이 최적화 문제.
  '값을 바꿔가며 '조건을 만족하는가?'를 결정하는 것'이 결정 문제.
• 절단기 높이가 10억까지 가능하니까 1부터 10억까지 완전탐색하면 절대 안된다.
• 이 문제를 결정 문제로 바꾸기 위해서는 절단기 높이 H를 최소 범위와 최대 범위 사이에서 이진 탐색 처럼 바꿔주며 판단해야 한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

static int N, M;
static vector<int> tteok;

int main() {
	cin >> N >> M;	
	tteok = vector<int>(N);
	for (int i = 0; i < N; ++i) cin >> tteok[i];

	sort(begin(tteok), end(tteok));	// for binary search!

	int left = 0, right = tteok[N - 1], mid;
	while (left <= right) {
		int tempSum = 0, mid = (left + right) / 2;
		for (int i = 0; i < N; ++i)	// 자를 수 있으면 값을 더해주고, 없으면 0.
			tempSum += (tteok[i] - mid > 0) ? tteok[i] - mid : 0;
		if (M == tempSum) { cout << mid << '\n'; break; }
		else if (M < tempSum) left = mid + 1;
		else right = mid - 1;
	}
}

• 최소범위 left는 0, 최대범위 right은 가장 긴 떡의 길이로 시작한다.
• mid는 left + right의 절반이며 이 값이 절단기의 높이가 된다.
• 자를 수 있는 떡은 자르고 남는 길이들의 합을 구하고 손님이 요구한 길이 M과 비교해서 일치하면 답을 출력하고, 작으면 right을 줄여주고, 크면 left를 늘려준다.