Binary search is a fundamental technique for efficiently locating an element in a sorted array or finding an optimal value in a monotonic space. The core idea is to maintain a search interval that shrinks until the desired position is identified. Rather than memorizing multiple templates, a single open-interval approach works for both ordinary binary search and binary search on answer, with clear separation between maximization and minimization problems.

Unified Binary Search Template

We keep two pointers left and right that form an open itnerval (left, right). The invariants are:

• All elements to the left of left satisfy a given predicate (for maximization) or do not satisfy it (for minimization).
• All elements to the right of right have the opposite property.

The loop continues while left + 1 < right, and after termination, left and right give the boundaries. The actual answer depends on the variant you need.

Last element satisfying predicate (maximization)

int findLast(int target) {
   int left = 0, right = n + 1;          // indices 1..n are valid
   while (left + 1 < right) {
       int mid = left + (right - left) / 2;
       if (predicate(mid, target))       // element at mid is "good"
           left = mid;
       else
           right = mid;
   }
   return left;   // index of last good element
}

First element satisfying predicate (minimization)

int findFirst(int target) {
   int left = 0, right = n + 1;
   while (left + 1 < right) {
       int mid = left + (right - left) / 2;
       if (predicate(mid, target))       // element at mid is "good"
           right = mid;
       else
           left = mid;
   }
   return right;  // index of first good element
}

The predicate is a function that returns true for the side we want to move toward. For example, to find the first element ≥ x, use predicate(mid, x) = (a[mid] >= x) with the minimization version. To find the last element ≤ x, use predicate(mid, x) = (a[mid] <= x) with the maximization version.

Floating‑Point Binary Search

The same open‑interval idea works for real numbers. The only difference is the termination conidtion: instead of left + 1 < right, we iterate until right - left > epsilon. We can still use the same logic for left and right as "last good" / "first bad".

double binarySearchFloat(double low, double high) {
   double left = low - 1.0, right = high + 1.0;   // slightly enlarge range
   const double EPS = 1e-7;
   while (right - left > EPS) {
       double mid = (left + right) / 2.0;
       if (check(mid))
           left = mid;      // for maximization
       else
           right = mid;
   }
   return left;   // approximate optimal value
}

Binary Search on Answer

Binary search on answer applies the same technique to the space of candidate answers. We choose a feasible interval [low, high] and define a check(x) function that returns whether answer x is achievable. The structure is identical to the integer template above.

Maximize the answer (feasible zone on the left)

int maxAnswer() {
   int left = low - 1, right = high + 1;
   while (left + 1 < right) {
       int mid = left + (right - left) / 2;
       if (check(mid)) left = mid;
       else right = mid;
   }
   return left;
}

Minimize the answer (feasible zone on the right)

int minAnswer() {
   int left = low - 1, right = high + 1;
   while (left + 1 < right) {
       int mid = left + (right - left) / 2;
       if (check(mid)) right = mid;
       else left = mid;
   }
   return right;
}

The only requirement is that check be monotonic: it transitions from true to false (or vice versa) exactly once over the interval. For maximization, check(mid) returns true for all feasible values and false for infeasible ones. For minimization, the roles are reversed — check(mid) returns true for infeasible and false for feasible (or you can simply swap the if branches).

This unified template reduces mental overhead and eliminates edge‑case errors common in other formulations. Stick to the (left, right) open interval and decide whether you are looking for the last good value (maximization) or the first good value (minimization) — the code writes itself.