Binary Search on Answer
In this page:
Idea
Rather than searching for a value's position in an array, this technique binary searches over the range of possible answers to a problem, testing each candidate answer for feasibility instead of comparing it to stored data directly.
Example: Idea
#include <iostream>
using namespace std;
int main() {
cout << "Binary search the range of possible answers, testing feasibility of each midpoint instead of searching an array";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Binary search the range of possible answers, testing feasibility of each midpoint instead of searching an array");
}
}print("Binary search the range of possible answers, testing feasibility of each midpoint instead of searching an array")#include <stdio.h>
int main() {
printf("Binary search the range of possible answers, testing feasibility of each midpoint instead of searching an array");
return 0;
}Login to try C/C++/Java code in the editor
Monotonic Condition
This only works when feasibility is monotonic — meaning if some candidate answer works, every easier candidate on one side of it also works, and every harder candidate on the other side doesn't. That monotonic boundary is exactly what binary search needs to eliminate half the candidates at each step.
Example: Monotonic Condition
#include <iostream>
using namespace std;
int main() {
cout << "Only works when feasibility is monotonic: if one candidate works, every easier candidate on one side also works";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Only works when feasibility is monotonic: if one candidate works, every easier candidate on one side also works");
}
}print("Only works when feasibility is monotonic: if one candidate works, every easier candidate on one side also works")#include <stdio.h>
int main() {
printf("Only works when feasibility is monotonic: if one candidate works, every easier candidate on one side also works");
return 0;
}Login to try C/C++/Java code in the editor
Capacity Example
A classic example is finding the minimum capacity (of a ship, a set of couriers, a Wi-Fi router, etc.) that can complete a task within given constraints — you can't check every possible capacity one by one efficiently, but you can binary search over the range of possible capacities.
Example: Capacity Example
#include <iostream>
using namespace std;
bool canShip(int weights[], int n, int capacity, int days) {
int daysNeeded = 1, load = 0;
for (int i = 0; i < n; i++) {
if (load + weights[i] > capacity) { daysNeeded++; load = 0; }
load += weights[i];
}
return daysNeeded <= days;
}
int main() {
int weights[] = {3, 2, 2, 4, 1};
cout << (canShip(weights, 5, 6, 2) ? "Feasible" : "Not feasible");
return 0;
}public class Main {
static boolean canShip(int[] weights, int capacity, int days) {
int daysNeeded = 1, load = 0;
for (int w : weights) {
if (load + w > capacity) { daysNeeded++; load = 0; }
load += w;
}
return daysNeeded <= days;
}
public static void main(String[] args) {
int[] weights = {3, 2, 2, 4, 1};
System.out.println(canShip(weights, 6, 2) ? "Feasible" : "Not feasible");
}
}def can_ship(weights, capacity, days):
days_needed = 1
load = 0
for w in weights:
if load + w > capacity:
days_needed += 1
load = 0
load += w
return days_needed <= days
weights = [3, 2, 2, 4, 1]
print("Feasible" if can_ship(weights, 6, 2) else "Not feasible")#include <stdio.h>
int canShip(int weights[], int n, int capacity, int days) {
int daysNeeded = 1, load = 0;
for (int i = 0; i < n; i++) {
if (load + weights[i] > capacity) { daysNeeded++; load = 0; }
load += weights[i];
}
return daysNeeded <= days;
}
int main() {
int weights[] = {3, 2, 2, 4, 1};
printf(canShip(weights, 5, 6, 2) ? "Feasible" : "Not feasible");
return 0;
}Login to try C/C++/Java code in the editor
Steps
The pattern is: pick reasonable lower and upper bounds for the answer, test the midpoint with a feasibility check function, and narrow the range toward feasible or infeasible values based on the result, just like standard binary search narrows toward a target.
Example: Steps
#include <iostream>
using namespace std;
int main() {
cout << "Pick lower/upper bounds for the answer, test the midpoint with a feasibility check, then narrow the range";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Pick lower/upper bounds for the answer, test the midpoint with a feasibility check, then narrow the range");
}
}print("Pick lower/upper bounds for the answer, test the midpoint with a feasibility check, then narrow the range")#include <stdio.h>
int main() {
printf("Pick lower/upper bounds for the answer, test the midpoint with a feasibility check, then narrow the range");
return 0;
}Login to try C/C++/Java code in the editor
Complexity
The overall running time is the number of binary search steps (O(log(range))) multiplied by however long the feasibility check itself takes to run — so this technique is only fast if the feasibility check is itself efficient.
Example: Complexity
#include <iostream>
using namespace std;
int main() {
cout << "Total time is O(log(range)) binary search steps times the cost of each feasibility check";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Total time is O(log(range)) binary search steps times the cost of each feasibility check");
}
}print("Total time is O(log(range)) binary search steps times the cost of each feasibility check")#include <stdio.h>
int main() {
printf("Total time is O(log(range)) binary search steps times the cost of each feasibility check");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: