Binary Search Explained Step by Step With Code

Binary search is the search you already use when you look up a word in a dictionary. You do not start at page one. You open near the middle, then jump left or right.

That one habit makes it wildly faster than checking every item. But it comes with a strict rule and one famous bug. Let me walk you through both.

What is binary search?

Binary search is a fast way to find a value in a sorted list. It looks at the middle item first. If that is the value, it is done. If not, it uses one fact to skip half the list.

Because the list is sorted, the middle item tells you which way to go. If your target is smaller than the middle, it has to be in the left half. If it is bigger, it has to be in the right half. So you throw the other half away and repeat on what is left.

That throwing away is the magic. Every step cuts the problem in half. This is why binary search shows up early in any DSA roadmap, right after linear search.

How does binary search work step by step?

Reading the idea is one thing. Watching the range shrink is another. So let’s search a real sorted list by hand.

Take the sorted list [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], with indexes 0 to 9, and search for 23. We track two edges, a low and a high, starting at 0 and 9.

The middle of 0 and 9 is index 4, which holds 16. Our target 23 is bigger than 16, so it must be to the right. We move low up to 5 and ignore the whole left half.

Now the range is 5 to 9. The middle is index 7, which holds 56. Our target 23 is smaller than 56, so it must be to the left. We move high down to 6. The range is now just 5 to 6. The middle is index 5, which holds 23. Found it, in only three checks.

Compare that to checking each item, which would have taken six. On a list of ten the gap is small. On a list of a million, it is the difference between 20 checks and a million.

Binary search code in Python and C++

The code keeps two edges and a loop. Each pass finds the middle, then moves one edge. Here it is in Python.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

The loop runs while the range is still valid. It returns the index on a match, or -1 if the value is never found. Here is the same logic in C++, the language most Indian placement tests expect.

int binarySearch(int arr[], int n, int target) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

What is the time complexity of binary search?

Binary search runs in O(log n) time. The log just means how many times you can halve the list before one item is left. For a list of a million items, that is about 20 steps. For a billion, only about 30.

That is the whole reason binary search matters. The list can grow huge while the work barely moves. The space is O(1) for the loop version, since it only tracks two edges. You can read the formal definition on Wikipedia’s binary search page.

Binary search vs linear search

The trade is simple to state. Binary search is far faster, but it has one hard rule. The list must be sorted. A linear search works on any list, sorted or not, but it may check every item.

So the choice depends on your data. If the list is already sorted, or you will search it many times, binary search wins easily. But if the list is unsorted and you only need one lookup, sorting it first can cost more than a plain scan. Binary search runs on a sorted array, where the instant index math lets it jump to any middle.

FAQ

What is the time complexity of binary search?

O(log n), because it halves the list on every step. A list of a million items takes about 20 checks. The space is O(1) for the loop version.

Does binary search need a sorted list?

Yes. This is its one strict rule. The whole method depends on knowing which half to keep, which only works when the list is in order.

What does binary search return when the value is missing?

Usually -1, or some signal for not found. The range shrinks until low passes high, the loop ends, and the code reports that the value is not there.

Why is binary search faster than linear search?

Because it throws away half the list each step instead of checking items one by one. That halving turns a million item search into about 20 checks rather than a million.

Can binary search be written with recursion?

Yes. You can write it with a loop or with recursion that calls itself on the smaller half. The loop version uses O(1) space, while the recursive version uses O(log n) for its calls.

What is the safe way to calculate the middle index?

Use low plus the quantity high minus low, divided by 2. This avoids the overflow that can happen when you add low and high directly on very large indexes.

So what should you remember?

Binary search is the dictionary trick written in code. Check the middle, decide which half can hold your target, and throw the other half away. Repeat until you find it.

It is blazing fast at O(log n), but only on sorted data. Get the middle calculation right, respect the sorted rule, and you have one of the most useful tools in computing.

Now try it. In a sorted list of 16 items, what is the most checks binary search would ever need to find a value?