용어 정의
정렬된 배열에서 특정 값을 찾을 때 반절씩 쪼개가면서 찾는 것
구현
int BinarySearch(vector<int> &a, int target) {
int left = 0;
int right = a.size() - 1;
while(right >= left) {
int mid = left + (right - left) / 2;
if(a[mid] == target) return mid;
else if (a[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}응용 : 일반화 이진탐색
특정 조건이 만족되기 시작하는 최초의 값을 찾기
예시 : C++의 std::lower_bound. 정렬된 배열 a에서 a[i] >= key를 만족하는 최소 인덱스 i를 반환한다. ⇒ i보다 크거나 같은 모든 인덱스 x에서 a[x] ⇒ key를 만족한다.
구현
bool check(int x) {// 조건 검증 함수... }
int GeneralBS(vector<int> &a, int key){
int left = 0;
int right = a.size() - 1;
while(right >= left) {
int mid = left + (right - left) / 2;
if(check(a[mid])) mid = right;
else mid = left;
}
return right;
}예시
나이 맞추기
초면인 사람이 자기 나이가 a살 이상 b살 미만이라 했다. 내가 물어보면 예/아니오로 답해준다. 나이를 맞추시오.
int GetAge(int a, int b) {
int left = a;
int right = b;
while(right >= left) {
int mid = left + (right - left) / 2;
if(나이가 mid 이하) mid = right;
else mid = left;
}
return right;
}사격왕
N개의 풍선이 초기 상태에 각각 Hi 에 있고, 1초마다 Si 씩 상승한다. 모든 풍선을 쏴서 터뜨리려고 하는데, 터뜨릴 때 풍선의 높이만큼 페널티가 발생한다. 최종 페널티는 발생한 페널티 중 최대 값이다. 가장 작은 페널티를 구하라.
// N개의 풍선이 있을 때, 모든 풍선을 터뜨리는 데 걸리는 시간은 N초임
// 초기 상태에서 N초 후에 가장 높게 있는 풍선의 높이가 최대 페널티임.
int FindShooter(int N, vector<int> &H, vector<int> &S){
int M = 0;
for(int i = 0; i<N; i++) M = max(M, H[i] + S[i] * N);
int left = 0, right = M;
while(right >= left) {
int mid = left + (right - left) / 2;
bool needSkip = false;
vector<long long> t(N, 0); // 각 풍선을 쏴야 하는 제한시간
for(int i = 0; i < N; i++) {
if(H[i] < mid) {
left = mid;
needSkip = true;
break;
}
else {
t[i] = (mid - H[i]) / S[i];
}
}
sort(t.begin(), t.end());
for(int i = 0; i < N; i++) {
if(t[i] < i) needSkip = true;
}
if(!needSkip) right = mid;
else left = mid;
}
return right;
}