Binary Search Explained Simply & Visually

Imagine you are playing a game where you try to guess a secret number from 1 to 10, and you have infinite attempts. You can choose random numbers (without repetition) — maybe you will get lucky and guess it on the first try, or it might take you all 10 tries to reach it. Or you can try to count all the numbers in order — 1, 2, 3, 4…— this is also going to take 10 guesses at max, but more systematic.

But what if you had to guess a number from 1 to 1000, or even maybe from 1 to a million? What about 1 and 10²⁰? As the range increases, it gets a lot harder to guess the secret number with brute force. 

Computer scientists also struggled with the same problem: how do you efficiently find something in a huge range? To address this issue, they came up with different methods, one of the most used is binary search.

Binary search works by dividing the range in half with each guess, and narrowing it down to determine whether the target lies in the lower or upper half of the range. And repeating this until the target value is reached.

Application

Let’s play a game to better understand how this works. I am going to pick a number between 1 to 100. Let’s say the number is 65. If you tried to guess the number by just counting — 1, 2, 3, 4, 5, 6, 7… — it would take you 65 tries to get it right in the worst case. Which is not efficient. 

Now let's try binary search: 

What we are going to do here is take the middle of each range. The first range is from 1 to 100, so we are going to compare 50 to 65. And as 65 is greater than 50, now we have eliminated all the numbers below 50. Our range is now 50 to 100.

In the second step, we are going to get the middle of the range between 50 to 100, which is 75. 65 is less than 75, so our range is going to be updated to 50 to 75.

Repeat the previous process: middle of the range 50 to 75 is 62.5, in this case, depending on your algorithm, you can either go to 62 or 63. I rounded it to 62. Since 65 > 62 → So the range is updated to 62 to 75.

We are going to get the middle of 62 to 75, which is 68.5; we went with 68. 65 < 68, so the range is 62 to 68.

Repeat the process, the middle of 62 and 68 is 65. And we finally found the secret number, congrats 🥳.

It took a total of 5 tries to guess the correct number. This was much efficient than the brute force method, which took 65 tries to reach this number. 

To summarize all this information into one formal definition: Binary search is an efficient algorithm for finding a target value within a sorted list by repeatedly dividing the search interval by half.

How Efficient is Binary Search?

Binary search runs in O(log n) time since we are eliminating half of the possible indices for each guess. Even if you are trying to find a number through a list of a billion numbers, it will only take 30 steps to find it: log_2 (1,000,000,000) = 30. 

The number of tries as the number of parameters changes could be seen here (x = n (number of elements), y = max number of tries):

Blue: y = n, linear search (counting in order)

Red: y = log_2 (n), binary search

Example Code Implementation

Python:

def binary_search(arr, target):
    bottom = 0
    top = len(arr) - 1
    
    while bottom <= top:
        mid = (bottom + top) // 2
        
        if arr[mid] == target: # If target is found
            return mid
        elif arr[mid] < target: # When the target value is greater than the middle
            bottom = mid + 1
        elif arr[mid] > target: # When the target value is less than the middle
            top = mid - 1

    return -1 # Target not found

binary_search([3, 5, 8, 19, 65], 19) # Example call