Medium · search

Binary Search

A million sorted numbers, twenty guesses. Binary search is the single highest-leverage algorithm in this whole problem set — and the one most often written subtly wrong.

At a glanceKeep lo and hi, halve the range with mid = (lo + hi) / 2, and return the 0-based index or -1 — the array is guaranteed sorted, so O(log n) replaces a linear scan.

Problem

Input: The first line is an integer n (1 ≤ n ≤ 10000). The second line holds n integers in strictly increasing order, separated by spaces. The third line is the value x to find.

Output: The 0-based index of x, or -1 if it isn't there.

Samples:

Input	Output
`5 1 3 5 8 9 8`	`3`
`5 1 3 5 8 9 7`	`-1`
`1 42 42`	`0`

A plain loop from 0 to n−1 gives the right answer too — but it looks at up to 10000 numbers where binary search looks at about 14. The tests are small; the habit is what matters.

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Think of a number between 1 and 100

You guess 50, I say "higher", and you instantly know the answer is not in 1–50. You just deleted half the possibilities with one question. That's the whole algorithm — the only thing the computer adds is doing it precisely with indices.

Hint 2 — Two pointers that close in

Keep lo and hi as the inclusive range that might still contain x. Look at mid = (lo + hi) / 2. If a[mid] is too small, everything left of it is too small too, so lo = mid + 1. If it's too big, hi = mid - 1. If it matches, you're done.

Hint 3 — The loop condition is the hard part

Use while (lo <= hi), not lo < hi. With <, a range of exactly one element never gets examined — so n = 1 always answers −1, even when the number is right there. And never write hi = mid: with lo <= hi that can loop forever.

Solution (try it first!)

#include <iostream>
using namespace std;

int a[10005];

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

    int lo = 0, hi = n - 1, ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] == x) { ans = mid; break; }
        else if (a[mid] < x) lo = mid + 1;
        else hi = mid - 1;
    }
    cout << ans << endl;
    return 0;
}

Fourteen comparisons to search ten thousand numbers; twenty to search a million. That's what O(log n) buys you, and it only works because the data is sorted — sortedness is information, and binary search is how you spend it. Real-world use: lower_bound in the C++ standard library is exactly this, and it's the inner engine of database indexes. The last problem, Maximum Subarray Sum, asks a different question: not "where is it" but "what's the best stretch of it".

Deep dive

Why this works

Guess 50, hear "too high", and half the possibilities are gone in one question. Binary search is just that move, made precise with indices.

The cost

O(log n): fourteen comparisons for ten thousand numbers, twenty for a million. A linear scan needs a million — fifty thousand times more work.

Where it goes wrong

Writing while (lo < hi) means a range holding exactly one element is never examined, so n = 1 always answers −1.
Writing hi = mid instead of hi = mid - 1 loops forever with lo <= hi — and freezes the tab.

Next step

The last problem changes the question: not "where is it" but "which stretch is best" — Maximum Subarray Sum.

Two things to remember

Sortedness is information; binary search is how you spend it.
The idea is easy — the lo <= hi and mid ± 1 boundaries are where it breaks.

🐞 This version fails — open it and try

lo < hi never examines a one-element range, so n = 1 always answers −1

#include <iostream>
using namespace std;

int a[10005];

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

    int lo = 0, hi = n - 1, ans = -1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (a[mid] == x) { ans = mid; break; }
        else if (a[mid] < x) lo = mid + 1;
        else hi = mid - 1;
    }
    cout << ans << endl;
    return 0;
}