Binary Search Algorithm Explained with Examples

By Khaled Md Tuhidul Hossain · 2025-07-10 · Algorithms

Binary search is one of those algorithms that seems trivial until you try to implement it correctly under pressure. The concept is straightforward: cut the search space in half each time. But off-by-one errors in the boundaries have caused more bugs than most people would like to admit.

The prerequisite is simple. Your data needs to be sorted. If it's not sorted, binary search won't work. That's the deal.

Interactive Visualization

Use the controls below to step through the algorithm or let it play automatically.

name: binary-search
input: {"array": [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], "target": 23}
speed: 500

How Binary Search Works

You have a sorted array and you're looking for a target value. Instead of checking every element from left to right (linear search), you look at the middle element first. If the middle element is your target, great, you're done. If the target is smaller, you know it must be in the left half. If it's bigger, it's in the right half. Now repeat with just that half.

Each comparison eliminates half the remaining elements. That's why it's O(log n) instead of O(n).

Visualizing the Search Space

Three comparisons to find our target in a 10-element array. A linear search might have needed 6. The difference gets dramatic with larger arrays. For a million elements, binary search needs at most 20 comparisons. Linear search could need a million.

Step-by-Step Walkthrough

Let's search for 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91].

Step 1

[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
 ^                                  ^
low=0                           high=9
                  ^
                mid=4
              arr[4]=16

16 < 23, so target is in the right half.
Move low to mid + 1 = 5.

Step 2

[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
                    ^               ^
                  low=5          high=9
                            ^
                          mid=7
                        arr[7]=56

56 > 23, so target is in the left half.
Move high to mid - 1 = 6.

Step 3

[2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
                    ^   ^
                  low=5 high=6
                    ^
                  mid=5
                arr[5]=23

23 == 23. Found it at index 5!

Three steps. Each time we cut the search space roughly in half. That's the power of logarithmic time.

How the Search Space Shrinks

Python Implementation

Iterative Version

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = low + (high - low) // 2  # Avoids integer overflow

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # Target not found


arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(arr, 23))   # 5
print(binary_search(arr, 15))   # -1

A couple of things to notice. We use low + (high - low) // 2 instead of (low + high) // 2. In Python this doesn't matter because integers can be arbitrarily large, but in languages like Java or C++ the addition can overflow. It's a good habit to keep.

The loop condition is low <= high, not low < high. That equals sign matters. Without it, you'd miss the case where the target is the last remaining element.

Recursive Version

def binary_search_recursive(arr, target, low=0, high=None):
    if high is None:
        high = len(arr) - 1

    if low > high:
        return -1

    mid = low + (high - low) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)


arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search_recursive(arr, 23))  # 5
print(binary_search_recursive(arr, 15))  # -1

The iterative version is generally preferred. It uses O(1) space while the recursive version uses O(log n) stack space. The logic is identical, you're just replacing the recursion with a while loop.

Useful Variations

Find the Leftmost (First) Occurrence

When duplicates exist, standard binary search might land on any one of them. This version finds the first occurrence.

def find_leftmost(arr, target):
    low = 0
    high = len(arr) - 1
    result = -1

    while low <= high:
        mid = low + (high - low) // 2

        if arr[mid] == target:
            result = mid       # Record this, but keep searching left
            high = mid - 1
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return result


arr = [1, 3, 3, 3, 5, 7, 9]
print(find_leftmost(arr, 3))  # 1 (first occurrence)

The trick is that when we find the target, we don't stop. We record the position and keep searching the left half for an even earlier occurrence.

Search Insert Position

This is a classic LeetCode problem. Find where a target would be inserted to keep the array sorted.

def search_insert(arr, target):
    low = 0
    high = 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 low  # This is the insertion point


arr = [1, 3, 5, 6]
print(search_insert(arr, 5))  # 2 (found at index 2)
print(search_insert(arr, 2))  # 1 (would insert at index 1)
print(search_insert(arr, 7))  # 4 (would insert at the end)

When the loop ends without finding the target, low points to exactly where it should go. This works because low always ends up at the first element greater than the target.

Binary Search on a Rotated Sorted Array

This is a trickier variation. The array was sorted but then rotated at some pivot. For example, [4, 5, 6, 7, 0, 1, 2] is [0, 1, 2, 4, 5, 6, 7] rotated at index 4.

def search_rotated(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = low + (high - low) // 2

        if arr[mid] == target:
            return mid

        # Figure out which half is sorted
        if arr[low] <= arr[mid]:
            # Left half is sorted
            if arr[low] <= target < arr[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:
            # Right half is sorted
            if arr[mid] < target <= arr[high]:
                low = mid + 1
            else:
                high = mid - 1

    return -1


arr = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(arr, 0))  # 4
print(search_rotated(arr, 3))  # -1

The key insight here is that in a rotated sorted array, at least one half is always properly sorted. We figure out which half is sorted, then check if the target falls within that sorted half. If it does, search there. If not, search the other half.

Time and Space Complexity

Best case is O(1) when the target happens to be the middle element on the first check. Worst and average cases are both O(log n) because we halve the search space each iteration.

Space is O(1) for the iterative version. The recursive version uses O(log n) due to the call stack.

To put the time complexity in perspective:

That difference is massive at scale.

When Should You Use Binary Search?

Finding elements in sorted arrays. This is the obvious one. If your data is sorted and you need to look things up repeatedly, binary search is the way to go. Python's bisect module uses binary search under the hood.

Searching in rotated sorted arrays. Databases and distributed systems sometimes deal with rotated or partially sorted data. The modified binary search handles this without needing to "un-rotate" the array first.

Finding boundaries. Questions like "what's the first number greater than X" or "what's the last number less than or equal to Y" are natural fits. These show up constantly in range queries and scheduling problems.

Searching on monotonic functions. Binary search doesn't just work on arrays. Any time you have a yes/no condition that flips from false to true (or true to false) as you move in one direction, you can binary search for the flip point. Square root calculation, finding minimum capacity, allocating resources, these all use this pattern.

Common Interview Problems

• Search in Sorted Array: The basic template. Make sure your boundaries are right.
• Search in Rotated Sorted Array: Determine which half is sorted, then decide where to look.
• Find First and Last Position: Use the leftmost/rightmost variation to find the range of a target.
• Search Insert Position: When the element isn't found, low gives you the insert point.
• Find Peak Element: Binary search works even when the array isn't fully sorted, as long as you can decide which direction to go.
• Sqrt(x): Binary search between 0 and x for the largest number whose square is less than or equal to x.

Binary search is one of those foundational tools you'll reach for over and over. Get the template solid in your head, understand the boundary conditions, and the variations become much easier to reason about.