All lessons
LESSON 36/53Searching and Sorting
Binary Search on the Answer
GOALGuess an answer and check it, instead of computing it directly.
This one is hard — be comfortable with the previous lesson first. The idea: sometimes computing the answer is difficult, but checking "is this answer possible?" is easy. When that is true you can binary search over the possible answers.
ON THIS PAGE
SHOW EXAMPLE IN
//THE EXAMPLE
main.cpp
#include <iostream>
#include <vector>
using namespace std;
// Can we cut k pieces of this length from the boards?
bool enough(const vector<int>& boards, int length, int k) {
int pieces = 0;
for (int b : boards) {
pieces = pieces + b / length;
}
return pieces >= k;
}
int main() {
vector<int> boards = {8, 12, 5};
int k = 4;
int lo = 1, hi = 12, best = 0;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (enough(boards, mid, k)) {
best = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
cout << best << endl;
return 0;
}> what you see
5
//LINE BY LINE
Watch it run
Three boards of length 8, 12 and 5. We need 4 equal pieces.
Recognising when to use it
The pattern: the problem asks for a largest or smallest value, you cannot compute it directly, but you CAN easily check whether a given value works.
- "What is the longest length possible?"
- "What is the smallest time needed?"
- "What is the most we can take?"
Always check first: does the answer change in one direction only? If 5 works, 4 must also work. If not, this method does not apply.