Binary Search

The problem and the algorithm

Problem: we have a sorted array a[0..n-1] in non-decreasing order. We want to find an index i such that a[i] == x.

Example: find x = 13 in [3, 5, 8, 13, 18, 19, 21, 27, 32]

Algorithm

1. Keep two pointers l and r representing the current search range
2. While l <= r:
   • Compute mid = (l + r) / 2
   • If a[mid] == x, return mid
   • If a[mid] < x, search the right half (l = mid + 1)
   • If a[mid] > x, search the left half (r = mid - 1)

Time complexity: at each step we halve the search space → O(log n).

Trace · x = 13

index:   0  1  2  3  4  5  6  7  8
a:       3  5  8 13 18 19 21 27 32

step    l    r  mid  a[mid]   
------------------------------------------------------
   1    0    8    4      18   18 > 13 → r = 3
   2    0    3    1       5   5 < 13 → l = 2
   3    2    3    2       8   8 < 13 → l = 3
   4    3    3    3      13   a[mid] == 13 → found at 3

4 steps, and the range shrinks 9 → 4 → 2 → 1. For a million elements binary search needs at most 20 steps; a linear scan needs up to a million.

Implementation

#include <iostream>
#include <vector>
using namespace std;

int binary_search_exact(vector<int>& a, int x) {
    int l = 0, r = (int)a.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;  // Avoids overflow
        if (a[mid] == x) return mid;
        if (a[mid] < x) l = mid + 1;
        else r = mid - 1;
    }
    return -1; // not found
}

int main() {
    vector<int> a = {3, 5, 8, 13, 18, 19, 21, 27, 32};
    int x = 13;
    int idx = binary_search_exact(a, x);
    cout << (idx != -1 ? "Found at index " + to_string(idx) : "Not found") << "\n";
    return 0;
}

Found at index 3

l + (r - l) / 2 is the same middle as (l + r) / 2, but l + r can overflow int when both are close to 2·10⁹.

Another version · returning the index

The same search with (l + r) / 2 and an else if chain. Returns the index, or −1.

#include <iostream>
#include <vector>

using namespace std;

int binary_search(vector<int> &a, int x) {
    int l = 0, r = a.size() - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] == x)
            return mid;
        else if (a[mid] > x)
            r = mid - 1;
        else
            l = mid + 1;
    }
    return -1;
}

int main() {
    vector<int> a = {3, 5, 8, 13, 18, 19, 21, 27, 32};
    int ind = binary_search(a, 13);
    cout << ind;
    return 0;
}

3

Another version · printing l and r

The same function with one extra line — cout << l << " " << r at the top of the loop — so the range can be watched shrinking. It reads the array and x from input.

#include <iostream>
#include <vector>

using namespace std;

int binary_search(vector<int> &a, int x) {
    int l = 0, r = a.size() - 1;
    while (l <= r) {
        cout << l << " " << r << endl;
        int m = (l + r) / 2;
        if (a[m] == x)
            return m;
        if (a[m] > x)
            r = m - 1;
        else
            l = m + 1;
    }
    return -1;
}

int main() {
    int n;
    vector<int> a;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        a.push_back(t);
    }
    int x;
    cin >> x;
    int ind = binary_search(a, x);
    cout << ind;
        
    return 0;
}

9
3 5 8 13 18 19 21 27 32
13

0 8
0 3
2 3
3 3
3

Practice problem · does x occur in the array?

Given an array and k queries, check whether each queried element exists. Codeforces EDU · Binary Search · A

#include <iostream>
#include <vector>
using namespace std;

bool find(vector<int> &a, int x) {
    int l = 0;
    int r = a.size() - 1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (a[m] == x)
            return true;
        if (a[m] < x) 
            l = m + 1;
        else
            r = m - 1;
    }
    return false;
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    int x;
    for (int i = 0; i < k; i++) {
        cin >> x;
        if (find(a, x))
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

5 3
1 3 5 7 9
3 4 9

YES
NO
YES

Another version · exists()

The same solution with the function called exists and the array read with push_back.

#include <iostream>
#include <vector>

using namespace std;

bool exists(vector<int> &a, int x) {
    int l = 0, r = a.size() - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] == x)
            return true;
        if (a[mid] > x) 
            r = mid - 1;
        else
            l = mid + 1;
    }
    return false;
}

int main() {
    int n, k, t;
    cin >> n >> k;
    vector<int> a;
    for (int i = 0; i < n; i++) {
        cin >> t;
        a.push_back(t);
    }
    for (int i = 0; i < k; i++) {
        cin >> t;
        if (exists(a, t))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

5 3
1 3 5 7 9
3 4 9

YES
NO
YES

Goal and algorithm

Goal: find

• the largest element ≤ x — the closest from the left
• the smallest element ≥ x — the closest from the right

Algorithm for the largest ≤ x

1. Add −∞ at the start and +∞ at the end — conceptually: l = -1, r = n
2. Maintain the invariant: a[l] ≤ x and a[r] > x
3. While l + 1 < r:
   • mid = (l + r) / 2
   • if a[mid] ≤ x → move l = mid
   • else r = mid

Trace · x = 20

index:   0  1  2  3  4  5  6  7  8
a:       3  5 10 11 13 18 25 27 31

step    l    r  mid  a[mid]   
------------------------------------------------------
   1   -1    9    4      13   13 ≤ 20 → l = 4
   2    4    9    6      25   25 > 20 → r = 6
   3    4    6    5      18   18 ≤ 20 → l = 5

The loop stops with l = 5, r = 6: a[l] = 18 is the largest element ≤ 20, a[r] = 25 the smallest element greater than 20.

Implementation

#include <bits/stdc++.h>
using namespace std;

pair<int,int> nearest_elements(vector<int>& a, int x) {
    int n = a.size();
    int l = -1, r = n; // conceptual -∞ and +∞
    
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (a[mid] <= x) l = mid;
        else r = mid;
    }
    
    int leftVal = (l >= 0 ? a[l] : INT_MIN);
    // a[r] is the smallest element > x; for the smallest element >= x
    // run the mirrored search: keep a[l2] < x and a[r2] >= x
    int l2 = -1, r2 = n;
    while (l2 + 1 < r2) {
        int mid = (l2 + r2) / 2;
        if (a[mid] < x) l2 = mid;
        else r2 = mid;
    }
    int rightVal = (r2 < n ? a[r2] : INT_MAX);
    return {leftVal, rightVal};
}

int main() {
    vector<int> a = {3, 5, 10, 11, 13, 18, 25, 27, 31};
    int x = 20;
    auto [leftVal, rightVal] = nearest_elements(a, x);
    cout << "Closest left: " << leftVal << ", closest right: " << rightVal << "\n";

    x = 18;
    auto [l18, r18] = nearest_elements(a, x);
    cout << "x = 18 -> left: " << l18 << ", right: " << r18 << "\n";
    return 0;
}

Closest left: 18, closest right: 25
x = 18 -> left: 18, right: 18

After the first loop a[r] is the smallest element strictly greater than x. When x itself is in the array that is the wrong answer for "≥ x": for x = 18 it would give 25. The second, mirrored loop keeps a[l2] < x ≤ a[r2] and gives 18.

Another version · closest to the left

Returns the index of the largest element ≤ x — l, or −1 if there is none. The program prints l + 1: the 1-based position, which is also how many elements are ≤ x.

int index_(vector<int> &a, int x) {
    int l = -1, r = a.size(); 
    while (r > l + 1) {
        int mid = (l + r) / 2;
        if (a[mid] <= x)
            l = mid;
        else
            r = mid;
        // cout << l << " " << r << " " << mid << endl;
    }
    return l;
}

#include <iostream>
#include <vector>

using namespace std;

int index_(vector<int> &a, int x) {
    int l = -1, r = a.size(); 
    while (r > l + 1) {
        int mid = (l + r) / 2;
        if (a[mid] <= x)
            l = mid;
        else
            r = mid;
        // cout << l << " " << r << " " << mid << endl;
    }
    return l;
}

int main() {
    int n, k, t;
    vector<int> a;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> t;
        a.push_back(t);
    }
    for (int i = 0; i < k; i++) {
        cin >> t;
        cout << index_(a, t) + 1 << endl;
    }
    return 0;
}

5 5
1 3 5 7 9
2 4 8 1 10

1
2
4
1
5

Another version · closest to the right

The mirrored search: a[mid] ≥ x moves r. Returns the index of the smallest element ≥ x — r, or n if there is none.

int index_right(vector<int> &a, int x) {
    int l = -1, r = a.size(); 
    while (r > l + 1) {
        int mid = (l + r) / 2;
        if (a[mid] >= x)
            r = mid;
        else
            l = mid;
        // cout << l << " " << r << " " << mid << endl;
    }
    return r;
}

#include <iostream>
#include <vector>

using namespace std;

int index_right(vector<int> &a, int x) {
    int l = -1, r = a.size(); 
    while (r > l + 1) {
        int mid = (l + r) / 2;
        if (a[mid] >= x)
            r = mid;
        else
            l = mid;
        // cout << l << " " << r << " " << mid << endl;
    }
    return r;
}

int main() {
    int n, k, t;
    vector<int> a;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> t;
        a.push_back(t);
    }
    for (int i = 0; i < k; i++) {
        cin >> t;
        cout << index_right(a, t) + 1 << endl;   // was index_(...), which is not defined here
    }
    return 0;
}

5 5
1 3 5 7 9
2 4 8 1 10

2
3
5
1
6

The idea

We are looking for the smallest (or largest) x such that some monotonic condition holds. Instead of searching an array, we search in the range of possible answers.

Example 1 · minimum square to fit rectangles

Problem: we have n rectangles of size a × b. Find the smallest side of a square that can fit all of them (no rotation).

Monotonic function: f(x) = (⌊x / a⌋ × ⌊x / b⌋ ≥ n). If a square of side x can fit them, a larger square can too → monotonic.

#include <iostream>
using namespace std;

bool canFit(long long side, long long a, long long b, long long n) {
    return (side / a) * (side / b) >= n;
}

long long minSquareSide(long long a, long long b, long long n) {
    long long l = 0, r = max(a, b) * n; // upper bound
    
    while (l + 1 < r) {
        long long mid = (l + r) / 2;
        if (canFit(mid, a, b, n)) r = mid;
        else l = mid;
    }
    return r;
}

int main() {
    long long n = 10, a = 2, b = 3;
    cout << "Minimum side: " << minSquareSide(a, b, n) << "\n";
    return 0;
}

Minimum side: 9

Check: side 9 holds 4 × 3 = 12 rectangles 2 × 3 — enough for 10; side 8 holds only 8.

Another version · long long throughout

The same solution reading w, h and n from input.

#include <iostream>
#define ll long long

using namespace std;

ll can_fit(ll n, ll w, ll h) {
    return (n / w) * (n / h);
}

ll solve(ll w, ll h, ll n) {
    ll l = 0; ll r = max(w, h) * n;
    while (l + 1 < r) {
        ll mid = (l + r) / 2;
        if (can_fit(mid, w, h) >= n)
            r = mid;
        else
            l = mid;
    }
    return r;
}


int main() {
    ll w, h, n;
    cin >> w >> h >> n;
    cout << solve(w, h, n);
    return 0;
}

2 3 10

9

Another version · with int and a trace

The first draft: prints l r mid at every step. It is written with int, which is enough for small inputs only — max(n, m) * k overflows when the numbers are large.

#include <iostream>

using namespace std;
int n, m, k;

bool f(int x) {
    return (x / n) * (x / m) >= k;
}

int solve(int n, int m, int k) {
    int l = 0;
    int r = max(n, m) * k;   // overflows int for large n, m, k — use long long
    while (l + 1 < r) {
        cout << l << " " << r << " " << (l + r) / 2 << endl;
        int x = (l + r) / 2;
        if (f(x) == true)
            r = x;
        else
            l = x;
    }
    return r;
}

int main() {
    cin >> n >> m >> k;
    cout << solve(n, m, k);
    return 0;
}

Example 2 · maximum rope length

Problem: we have n ropes and want k equal pieces of the maximum length.

Monotonic function: f(x) = can we cut ≥ k pieces of length x? If we can cut pieces of length x, we can cut shorter ones too → monotonic decreasing, so the search keeps the largest x that is still true.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

bool canCut(const vector<double>& ropes, double len, int k) {
    long long count = 0;
    for (double r : ropes) 
        count += (long long)(r / len);
    return count >= k;
}

double maxRopeLength(vector<double>& ropes, int k) {
    double l = 0, r = *max_element(ropes.begin(), ropes.end());
    
    for (int iter = 0; iter < 100; iter++) { // enough iterations for precision
        double mid = (l + r) / 2;
        if (canCut(ropes, mid, k)) l = mid;
        else r = mid;
    }
    return l;
}

int main() {
    int n, k;
    cin >> n >> k;
    
    vector<double> ropes(n);
    for (int i = 0; i < n; i++) {
        cin >> ropes[i];
    }
    
    cout << fixed << setprecision(2) << "Max length: " << maxRopeLength(ropes, k) << "\n";
    return 0;
}

// Example input:
// 4 11
// 802
// 743
// 457
// 539

4 11
802
743
457
539

Max length: 200.50

Another version · stop by precision

Instead of 100 iterations the loop runs while r − l > eps with eps = 1e-8, starting from r = 1e9.

#include <iostream>
#include <vector>

using namespace std;

double eps = 1e-8;

bool ok(vector<double> &a, int n, double t) {
    int p = 0;
    for (int i = 0; i < a.size(); i++)
        p += (int) (a[i] / t);
    return p >= n;
}

double solve(vector<double> &a, int n) {
    double l = 0, r = 1e9;
    while (r - l > eps) {
        double mid = (l + r) / 2.0;
        if (!ok(a, n, mid)) 
            r = mid;
        else
            l = mid;
    }
    return l;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<double> a;
    for (int i = 0; i < n; i++) {
        double q;
        cin >> q;
        a.push_back(q);
    }
    cout << solve(a, k);
    return 0;
}

4 11
802
743
457
539

200.5

Another version · cube root

A real-valued answer with nothing to cut: the cube root of x. f(y) = y³ grows, so find the point where it reaches x, with precision eps = 1e-3. The loop prints the range and f(mid) at every step.

#include <iostream>

using namespace std;
double x;
double eps = 1e-3;

double f(double y) {
    return y * y * y;
}

double solve(double x) {
    double l = 0, r = max(1.0, x);   // for x < 1 the cube root is bigger than x
    while (r - l > eps) {
        cout << l << " " << r << " " << (l + r) / 2.0 << endl;
        double y = (l + r) / 2;
        cout << f(y) << endl;
        if (f(y) >= x)
            r = y;
        else
            l = y;
    }
    return l;
}

int main() {
    cin >> x;
    cout << solve(x);
    return 0;
}

The upper bound must contain the answer: for x < 1 the cube root is bigger than x (∛0.125 = 0.5), so r = x is not enough — r = max(1.0, x) is.

Five things to remember

1. Binary search works on sorted data or monotonic conditions
2. Search the answer space: sometimes we search not an array but a range of possible answers
3. Floating point precision: when the answer is a floating point number, iterate a fixed number of times (e.g. 100) to avoid infinite loops
4. Always define a clear monotonic function f(x) before implementing binary search on the answer
5. Time complexity: O(log n) for array search, O(log(max − min) × cost of f) for answer search

Four variants

The code on this page writes lower bound, upper bound and answer search in the other common style — l = -1, r = n, while (l + 1 < r), with a[l] and a[r] always on opposite sides of the boundary. Both styles are correct; pick one and keep its invariant.

Problem to topic