Binary Search

You've been doing this your whole life, now let's write it in code

🎯In the Real World...

Think about the last time you looked up a word in a physical dictionary. Did you start from page 1 and flip every single page? No, you opened somewhere in the middle, checked if you went too far or not far enough, and adjusted. That instinct IS binary search. You already know this algorithm. We're just going to write it in code.

The guessing game you already play
Imagine I'm thinking of a number between 1 and 1,000,000. You can ask "higher or lower?" after each guess.
Your first guess would be 500,000, right? Not 1. Not 999,999. The middle.
Why? Because one answer, "higher" or "lower", instantly eliminates HALF the possibilities.

Guess 500,000 → "higher" → now you only need to search 500,001 to 1,000,000

Guess 750,000 → "lower" → now you only need 500,001 to 749,999

Each step cuts the problem in half

This is binary search. In a sorted list of 1,000,000 items, you find anything in at most 20 guesses. Not 1,000,000. Twenty.

The only three things that can happen at each step:
1. The middle element IS the target → done, return the index2. The middle element is TOO SMALL → target must be to the RIGHT → move left boundary up3. The middle element is TOO BIG → target must be to the LEFT → move right boundary down
That's the whole algorithm. Three decisions. One loop.

Let's trace through a real example together
Array: [1, 3, 5, 7, 9, 11, 13, 15] Target: 7Indices: 0 1 2 3 4 5 6 7
Step 1: lo=0, hi=7. Middle index = (0+7)//2 = 3. nums[3] = 7. Is 7 == 7? Yes! Found it. Return 3.
That was lucky, let's try a harder one. Target: 11
Step 1: lo=0, hi=7. mid=3. `nums[3] = 7`. Is 11 > 7? Yes → search the RIGHT half. lo = 3+1 = 4Step 2: lo=4, hi=7. mid=5. nums[5] = 11. Is 11 == 11? Yes! Found it. Return 5.
Target: 6 (not in the array)
Step 1: lo=0, hi=7. mid=3. `nums[3]=7`. 6 < 7 → search LEFT. hi = 3-1 = 2Step 2: lo=0, hi=2. mid=1. `nums[1]=3`. 6 > 3 → search RIGHT. lo = 1+1 = 2Step 3: lo=2, hi=2. mid=2. `nums[2]=5`. 6 > 5 → lo = 2+1 = 3Step 4: lo=3 > hi=2. Loop ends. Return -1 (not found).

Binary search, now the code makes sensepython

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1   # Start: full array

    while lo <= hi:              # Keep going while there's still a search space
        mid = lo + (hi - lo) // 2  # Middle of current search space

        if nums[mid] == target:   # Decision 1: Found it!
            return mid
        elif nums[mid] < target:  # Decision 2: Too small → go right
            lo = mid + 1
        else:                     # Decision 3: Too big → go left
            hi = mid - 1

    return -1  # Search space collapsed, target not in array

# Try it
nums = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(nums, 11))  # → 5
print(binary_search(nums, 6))   # → -1

Why lo + (hi - lo) // 2 instead of (lo + hi) // 2?
Both give the same result for normal-sized arrays. But if lo and hi are both very large numbers (like 2 billion), lo + hi can overflow the integer limit in languages like Java or C++. lo + (hi - lo) // 2 avoids that. In Python integers don't overflow, but it's a good habit to write it the safe way.

Gotcha: what if there are duplicates?
Standard binary search finds A match, not necessarily the FIRST or LAST one. If you have [1, 3, 3, 3, 5] and search for 3, you might land on index 1, 2, or 3 depending on the array size.
For "find the first occurrence" or "find the last occurrence", you need a modified version, that's the next exercise.

🤔Quick Check

Binary search requires the array to be sorted. What breaks if it's not?

Practice Exercises

0/3 solved

Understand First

Step 1 / 4

Implement Binary Search

You already play this game every time you look something up in a dictionary, or guess a number. The brain naturally jumps to the middle, not the beginning. Now let's translate that instinct into three lines of code.

Start with the full array in view

Set lo (left boundary) to index 0 and hi (right boundary) to the last index. Your search space is the whole array.

nums = [1, 3, 5, 7, 9, 11, 13, 15] → lo=0, hi=7

Exercise 2 of 3mediumGuided

⏱ 00:00

Find First Occurrence

Given a sorted array with possible duplicates and a target, return the index of the first occurrence of the target. Return -1 if not found.
[1, 2, 2, 2, 3, 4], target=2 → 1 (first 2 is at index 1)[1, 3, 5, 7], target=6 → -1

solution.py

2 / 3

Exercise 3 of 3hard

⏱ 00:00

Search in Rotated Array

A sorted array was "rotated", the last few elements were moved to the front.[1,2,3,4,5,6,7] rotated becomes [4,5,6,7,1,2,3]
At any midpoint, one half is always sorted, use that to decide which half could contain your target.
[4,5,6,7,0,1,2], target=0 → 4[4,5,6,7,0,1,2], target=3 → -1

solution.py

3 / 3

Solve all 3 exercises to unlock completion

Previous Next