Binary Search

Binary search is pretty efficient in searching an element in a sorted array. However, implementing a binary search algorithm is very tricky. It has many details, and if you fail one of them, your algorithm is not going to work properly.

In this article, I summarize my strategy to binary search algorithms. I hope it is helpful to you.

The 0-1 Binary Search Problem

Before the real problem, let’s think about a more fundamental binary search problem, the 0-1 binary search problem.

You are given an array like this [0, 0, 0, ..., 0, 0, 1, 1, 1, ..., 1, 1, 1], i.e., a couple of 0s followed by a couple of 1s. Find the index of first element 1. If not exist, return -1.

This is not a very challenging problem, here’s my solution to it.

def zero_one_binary_search(a):
    l = 0
    r = len(a) - 1

    while l < r:
        m = (l + r) // 2

        if a[m] == 1:
            r = m
        else:
            l = m + 1

    return l if a[l] == 1 else -1

Note that you can replace m = (l + r) // 2 with m = (r - l) // 2 + l to avoid int overflow, but I’d prefer to keep code simple here since the int overflow probably won’t happen in most cases.

Tackle Arbitrary Binary Search Problem

Now, let’s assume you are given a binary search problem to search first element in the array b, that meets the condition f.

• f(b[i]) = 1 means the condition is met.
• f(b[i]) = 0 means the condition is not met.

Before tackling this problem, let’s define another array c = [f(b[0]), f(b[1]), ... ]. To rephrase the above problem, we are really tring to find the first element in c which is 1. This is exactly the 0-1 binary search problem. So let’s reuse its solution here to address this question.

def binary_search_template(b):
    l = 0
    r = len(b) - 1

    while l < r:
        m = (l + r) // 2

        if f(b[m]) == 1:
            r = m
        else:
            l = m + 1

    return l if f(b[l]) == 1 else -1

That being said, all you have to do to tackle an arbitrary binary search problem is to define your binary search condition into a function f to map the target array into the 0-1 array.

An Example

Let’s take one concrete example, find the first element greater than k in the target array b.

In this case, we want every element greater than k to be mapped to 1, and everything else mapped to 0. we can define function f as this

def f(x):
    return x > k

By doing that, we map the array b into a 0-1 array, and together with binary_search_template. It’ll give us the solution to the problem. Here’s the final code

def find_first_element_greater_than(b, x):
    l = 0
    r = len(b) - 1

    while l < r:
        m = (l + r) // 2

        if b[m] > x:
            r = m
        else:
            l = m + 1

    return l if b[l] > x else -1