Binary Search

Binary search is a fast way to find something in a sorted list or range.
But before we get to that, let’s start with something simpler — linear search.

Linear search

Imagine you have a list of numbers and you want to check if a number is in the list.
The most natural thing to do is to look through the list one by one.

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

int main() {
    vector<int> arr = {4, 8, 15, 16, 23, 42};
    int target = 15;

    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            cout << "Found at index " << i;
            return 0;
        }
    }
    cout << "Not found";
}

This is called linear search because you move linearly through the list.
It always works, but if the list is long, it can be slow — you might need to check every element.

If there are a million numbers, that’s a million checks.

Now imagine you’re looking for a name in a printed phone book.
You wouldn’t start from the first page and read one by one.
You’d open somewhere in the middle, see if you’re too early or too late alphabetically, and then skip half the pages.

That’s binary search.

The idea of binary search

Binary search is like playing the ‘guess the number’ game.
Each time, you pick the middle value and ask:

Is this too small?
Too big?
Or exactly right?

Then you cut the search space in half.
This makes it much faster than linear search, but it only works if the data is sorted.

Classic binary search

Find the 7

We are given a sorted array

[1, 3, 5, 6, 7, 9, 11]

Find number 7 in the array if it exists and print the index it is on.

Solution

We start with the full range, then repeatedly narrow it down.

First, we find the element in the middle. This happens to be number 6. We ask whether number 7 is smaller or greater than number 6 - and it is greater. Since the array is sorted, this means that number 7 will be strictly after number 6 in the array. We can discard the first half of the array, because we know 7 cannot be before 6.

The array we are looking at now is [7, 9, 11]. The element in the middle is number 9. Number 7 is smaller than number 9. This means that 7 is before 9 in the sorted array. We can then discard 9 and anything that is right of 9.

Finally, our array is [7]. The middle element is 7, which is exactly what we are looking for. We asked three times to compare numbers: - We compared 6 and 7 - We compared 9 and 7 - We compared 7 and 7

So this is 3 comparisons. In the linear search, we would do at least 5. Already on smaller examples, we see that binary search brings significant improvement.

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

int main() {
    vector<int> arr = {1, 3, 5, 6, 7, 9, 11};
    int target = 7;
    int left = 0, right = arr.size() - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            cout << "Found at index " << mid;
            return 0;
        } else if (arr[mid] < target) 
            left = mid + 1;
        else 
            right = mid - 1;
    }

    cout << "Not found";
}

Output:

Found at index 4

Each step cuts the range in half.
If there are n elements, binary search only needs about \(\log_2(n)\) steps.
That’s around 20 checks, even if there are a million numbers.

Finding first element greater than or equal to X

Binary search can do more than find a number.
You can use it to find positions or boundaries.

Position Hunt

You are given an array [2, 4, 6, 8, 10]. Find the first element greater than or equal to 7 using the binary search method.

Solution

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

int main() {
    vector<int> arr = {2, 4, 6, 8, 10};
    int x = 7;

    int left = 0, right = arr.size() - 1;
    int ans = -1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] >= x) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    if (ans == -1) cout << "No element found";
    else cout << "First element >= " << x << " is at index " << ans;
}

Output:

First element >= 7 is at index 3

That means arr[3] = 8 is the first element greater than or equal to 7.

Algorithm

Start with two pointers, left and right.
Find the middle index mid.
If the middle value is the answer, stop.
If it’s too small, move left to mid + 1.
If it’s too big, move right to mid - 1.
Repeat until left > right.