[In Progress]二分查找Binary Search

Binary search is an efficient divide‑and‑conquer algorithm used to locate values or find optimal solutions. It repeatedly halves the search interval by comparing the middle element with a target/condition, cutting off impossible candidates each iteration.

Time complexity: \(\boldsymbol{O(\log n)}\) (much faster than linear search \(O(n)\))

Standard Binary Search

• Find a target value or its index in a sorted array/sequence.
• Find the first/last occurrence of a value.
• Check if a value exists in sorted data.

Binary Search on Answer (Contest‑Most‑Used)

• Solve optimization problems: find the minimum valid value or maximum valid value.
• Common scenarios: minimal time, minimal cost, maximal load capacity, maximum number of objects.
• Used when the answer is a number in a continuous range, not an element in an array.

Three non‑negotiable properties:

1. Monotonicity (Most Critical)Validity changes uniformly:
   • For minimal valid answer: If x is valid, all values larger than x are valid; if x is invalid, all smaller values are invalid.
   • For maximal valid answer: If x is valid, all smaller values are valid; if x is invalid, all larger values are invalid.
2. VerifiabilityWe can write a fast check() function (\(O(n)\) or \(O(\log n)\)) to judge whether a candidate answer is feasible.
3. Bounded RangeThe answer has clear lower (low) and upper (high) bounds.

// Return index of target; return -1 if not found
int binarySearch(vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2; // avoid integer overflow
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

#include <iostream>
using namespace std;
typedef long long ll;

// Custom feasibility check: return true if candidate x is valid
bool check(ll x) {
    // Write problem‑specific logic here
    return true;
}

// Find the minimal valid answer in [low, high]
ll findMinAnswer(ll low, ll high) {
    while (low < high) {
        ll mid = low + (high - low) / 2;
        if (check(mid)) high = mid;
        else low = mid + 1;
    }
    return low;
}

ll findMaxAnswer(ll low, ll high) {
    while (low < high) {
        ll mid = low + (high - low + 1) / 2; // ceiling division
        if (check(mid)) low = mid;
        else high = mid - 1;
    }
    return low;
}

C++ STL Built‑in Binary Search (Shortcut)

#include <algorithm>
// Check existence
binary_search(a.begin(), a.end(), target);
// First element >= target
lower_bound(a.begin(), a.end(), target);
// First element > target
upper_bound(a.begin(), a.end(), target);

Critical C++ Notes

1. Use long long for large value ranges to avoid overflow.
2. Always compute mid = low + (high‑low)/2 instead of (low+high)/2. 数学上完全等价，\(low + \frac{high-low}{2} = \frac{low+high}{2}\)，但是(low+high)/2 会爆炸（溢出）
3. Use low <= high for array search; use low < high for binary search on answer.

https://dmoj.ca/problem/coci11c5p2

https://dmoj.ca/problem/coci12c3p4

https://dmoj.ca/problem/champions

https://dmoj.ca/problem/coci06c5p6

https://dmoj.ca/problem/ioi11p3io

https://dmoj.ca/problem/coci20c6p5

https://dmoj.ca/problem/bsfast