The guessing game

Let's learn binary search today. And honestly once you see it, you will wonder how you never thought of it yourself. It is that natural.

binary search — cut it in half

3
[0]
7
[1]
12
[2]
19
[3]
24
[4]
31
[5]
38
[6]
45
[7]
52
[8]
61
[9]
74
[10]
88
[11]
size: 12
window: —
mid: —
enter a number above and press search

Okay so you have probably played this game as a kid. I am thinking of a number and it is somewhere in here:

3, 7, 12, 19, 24, 31, 38, 45, 52, 61, 74, 88

You do not know which one. But you know it is somewhere in this list.

Now you guess the middle. Which is 31. I say too high.

Now you know something. It is not 31. And it is not anything above 31 either. So your world just got smaller:

3, 7, 12, 19, 24

You guess the middle again. Which is 12. I say too low.

Everything below 12 is also gone now:

19, 24

You guess 19. Too high. One left:

24

Found it.

See what just happened? Every guess you threw away half. You never went one by one. And your world kept getting smaller and smaller until there was only one place left to look.

That is binary search.

💡 One thing you need
The list has to be sorted. When I said too high, you knew to look left because the numbers are in order. If they were all over the place that would not work. Binary search only works on a sorted list.

How it works in code

Say we have our numbers:

int arr[] = {3, 7, 12, 19, 24, 31, 38, 45, 52, 61, 74, 88};

We want to find 24.

The code needs to remember where it is looking. So we give it two things. Where it starts and where it ends.

int left = 0;
int right = n - 1;

Left starts at the very first number. Right starts at the very last.

Now we keep going as long as there is still something to look at. Every guess the window gets smaller. At some point left and right meet. And when they cross, the window is gone. Nothing left to look at.

while (left <= right)

Each time we look at the middle of whatever is left.

int mid = left + (right - left) / 2;

We check. Is this the number?

if (arr[mid] == target)
    return mid;

Found it. Done.

Too high? Right moves in. Everything above mid is gone.

else if (arr[mid] > target)
    right = mid - 1;

Too low? Left moves in. Everything below mid is gone.

else
    left = mid + 1;

And when left crosses right, there is nothing left to look at. The number was never there.

return -1;

And here is the whole thing together:

int binarySearch(int arr[], int n, int target) {
    int left = 0;
    int right = n - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            right = mid - 1;
        else
            left = mid + 1;
    }

    return -1;
}

How fast is it?

With linear search, 1000 numbers meant 1000 steps in the worst case. With binary search, 1000 numbers takes about 10 steps. A million numbers takes about 20 steps. You are halving every single time so the steps stay tiny even when the list gets huge.

Time complexity
That is why we say binary search is O(log n). Every step you throw away half. The list can grow enormously but the number of steps barely moves.

When to use binary search

When your list is large and sorted. That is really it. If you have a million numbers and you are searching through them again and again, binary search is the one you want.

But if your list is unsorted, you cannot use it directly. You would need to sort first. And sorting takes time. So if you are only searching once, sometimes linear search is still the simpler choice. It depends on the situation.

And that is binary search. Simple idea, powerful result. Just like that number guessing game you played as a kid, you were already doing it. You just did not know it had a name.