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
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) // 2with
m = (r - l) // 2 + lto 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(b[i]) = 1means the condition is met.
f(b[i]) = 0means the condition is not met.
Before tackling this problem, let’s define another array
c = [f(b), f(b), ... ]. 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
Let’s take one concrete example, find the first element greater than
k in the target array
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