Binary Search Explained Simply & Visually

What is Binary Search

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 counting all the numbers in order—1, 2, 3, 4…—this will still take 10 guesses max, but in a more systematic way.

But what if you had to guess a number from 1 to 1000, or even 1 to a million? What about 1 to 10²⁰? As the range increases, brute force becomes impractical.

Computer scientists faced the same problem: how do you efficiently find something in a huge range? One commonly used solution is binary search.

Binary search works by dividing the range in half with each guess, determining whether the target lies in the lower or upper half, and repeating the process until the target is found.

Application

Let’s play a game to better understand binary search. Imagine a number between 1 and 100. Let’s say the number is 65.

If you guessed sequentially—1, 2, 3, ...—it could take 65 tries in the worst case, which is inefficient.

Now let's try binary search:

We take the middle of the range each time.

1. First range: 1 to 100 → Middle = 50
   • Since 65 > 50, we eliminate numbers below 50, updating the range to 50 to 100.

1. New range: 50 to 100 → Middle = 75
   • Since 65 < 75, we update the range to 50 to 75.

1. Middle of 50 to 75 = 62
   • Since 65 > 62, new range: 62 to 75.

1. Middle of 62 to 75 = 68
   • Since 65 < 68, new range: 62 to 68.

1. Middle of 62 to 68 = 65
   • Found the target number! 🎉

Total tries: 5 (compared to 65 using brute force). Much more efficient!

How Efficient is Binary Search?

Binary search runs in O(log n) time, eliminating half of the possibilities with each guess.

For example:

• Searching through 1 billion numbers takes only 30 steps: log_2(1,000,000,000) ≈ 30

Graphical Comparison

• Linear search (blue line): y = n (counting sequentially)
• Binary search (red line): y = log_2(n)

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:  # Target is greater than the middle
            bottom = mid + 1
        else:  # Target is less than the middle
            top = mid - 1

    return -1  # Target not found

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