Binary search targets the boundary between two segments of a range rather than relying on monotonicity. While monotonic data guarantees applicability, non-monotonic data may still permit binary partitioning if a predicate cleanly divides elements into satisfying and non-satisfying groups.

Integer Binary Search

Integer binary search resolves positions where a condition changes from true to false across consecutive indices. Two canonical templates locate the leftmost and rightmost positions of interest.

The process involves:

• Repeatedly halving an interval [l, r] until l == r.
• A predicate test(pos) determines whether pos meets a target property.
• Depending on the template, update rules differ so that the invariant interval always contains the desired index.

Template A — Locate Last True Position

Interval split: [l, mid-1] (false side), [mid, r] (true side).

#include <iostream>
using namespace std;

bool test(int idx) {
    /* predicate returning true if idx satisfies the condition */
}

int find_last_true(int left, int right) {
    while (left < right) {
        int center = (left + right + 1) / 2;
        if (test(center))
            left = center;
        else
            right = center - 1;
    }
    return left;
}

Template B — Locate First True Position

Interval split: [l, mid] (true side), [mid+1, r] (false side).

int find_first_true(int left, int right) {
    while (left < right) {
        int center = (left + right) / 2;
        if (test(center))
            right = center;
        else
            left = center + 1;
    }
    return left;
}

Key distinctions:

• In Template A, center uses (left + right + 1)/2 to avoid infinite loops when left and right difffer by 1.
• In Template B, center uses (left + right)/2.
• Loop exitss when left == right, which is the sought index.

Correct application requires identifying which segment boundary is needed and defining test() accordingly. If no element satisfies the condition exactly, the returned index may represent a strict < or > relation instead of an exact match.

Floating-Point Binary Search

Floating-point searches sidestep discrete boundary concerns. Iteration continues until the interval width becomes negligible, at which point the midpoint approximates the solution.

Example: computing square root of a given value x:

#include <iostream>
using namespace std;

int main() {
    double num;
    cin >> num;
    
    double low = 0.0, high = num;
    for (int step = 0; step < 100; ++step) {
        double mid = (low + high) / 2.0;
        if (mid * mid > num)
            high = mid;
        else
            low = mid;
    }
    cout << low << endl;
    return 0;
}

Here, updates are always low = mid or high = mid because floating-point precision makes off-by-one adjustments unnecessary. After sufficient iterations, low converges to the square root approximation.

Problem-Solving Insights

• When working with arrays indexed 0..n-1, examine relationships between index positions and stored values to detect missing entries.
• Leverage all given constraints to shape the predicate and reduce search space effectively.