yet
another
tech
blog

How to Never Mess Up Binary Search

· 5 min read

Introduction

Binary search is one of the first algorithms that anyone learns.

We all know how it goes, mid = low + high // 2, while low <= high, right?

What Can Go Wrong

This is a perfectly good looking binary search implementation at first glance.

python
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if condition(mid):
        high = mid
    else:
        low = mid + 1
return mid

The Subtle Bug

This actually results in an infinite loop!

When low == high and condition(mid) == true, low and high always remain equal.

Binary search is full of these kinds of small pitfalls.

  • Off by one errors
  • Infinite loops
  • Incorrect returns (is it return mid or high or low)?

A Reduction

There is this (easy) LeetCode question called First Bad Version, that basically says

Find the first True in an array that looks like

[False, False, ... False, True ..., True, True, True]

This is exactly how a monotonic condition looks when applied to an array. The condition is False and then True for the rest of the array.

My claim:

Almost all binary search problems can be reduced to this question

So all we really need to do is solve this one question and then apply this reduction!

Solving First Bad Version

I recommend the solution below.

python
ans = -1
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if condition(mid):
        # Found True
        ans = mid
        # Look left for an earlier one 
        high = mid - 1
    else:
        # Look right for a True
        low = mid + 1
return ans
  • No infinite loops - high is reduced or low is increased
  • No confusion about return - use an additional ans variable, and always return that

Using This Solution For All Problems

All we need to do is tweak the condition() function now.

Example 1

Let’s think of the question:

Find the first number in the array strictly bigger than target

The condition function becomes:

python
def is_strictly_greater_than(mid):
    return arr[mid] > target

Example 2

Another example - Find target in a sorted array

python
def is_greater_than_or_equal(mid):
    return arr[mid] >= target

The first True lands on the first element >= target. If arr[ans] == target, we found it.

Example 3 - Inverted Array

This one is a little tricky - Find the last number smaller than target

It is easier to think of the condition arr[mid] < target, but this would convert the array to [True, True, ..., False, False].

So we flip the condition to arr[mid] >= target, which gives us [False, False, ..., True, True] — matching our template.

python
def condition(mid):
    return arr[mid] >= target
# answer is at index ans - 1

Author’s Note

This is my preferred way of writing binary search, and it has served me very well across the years. This is by no means the only template that works, but it’s the template I can write with no fear of errors.

Try it out in a couple of LeetCode problems, it will just roll off your fingers soon.

References