# Binary Search

This article give you a definitive guide to tackle any binary search problems easily.

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 `0`s followed by a couple of `1`s. 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
``````