Binary search is a essential algorithm used in coding interview. It is used to search for an target element x in a sorted list a: list with a time complexity O(log(n)). The naive way to search for x in a is to iterate through the list and check if a[i] == x for every i in range(len(a)). The time complexity of such an naive approach is O(n). However, if the list is not sorted, we can sort it first sort it first with a time complexity of O(nlog(n)) and then followed by a binary search. Thus if you are just going to do one search, it is better to just go with the naive approach. However, if you are search more than O(log(n)) times, then it might be better to first sort the list and then do binary search.

The general idea of binary search is to rule out half of the list at every iteration. Since the given list is sorted, we can tell which half to rule out by comparing the target element x with the element in the middle of the list. Since the length of the list is halved at every iteration, you will end up with a list of length 1 at roughly the log(n)-th iteration. In each iteration, you only do one comparison. Thus the time complexity of the algorithm is O(log(n)).

Bisection without worrying about edge cases

The idea of binary search is simple. However, there are some edge cases that need to be handled. For example, what if the target element x does not exist in the list a? Or what if there are multiple x in a? These are things that we do not want to worry about when implementing binary search, especially when we are doing it in an interview. Most certainly, we will introduce bugs when we are under pressure.

A stress-free way to implement binary search is alter the problem slightly. Instead of finding the target element x in a, the algorithm will slice the list a into three parts (p_less = a[:l], p_equal = a[l:r], p_greater = a[r:]) which satisfy the following assertions:

assert all(c < x  for c in p_less   ) == True
assert all(c == x for c in p_equal  ) == True
assert all(c > x  for c in p_greater) == True

All edges cases are automatically handled because p2 could be empty or contain multiple x. The output of the algorithm are now the two indices l and r that divide a into three parts.

This is exactly how the built-in bisect library works in Python. The pointer l is calculated by bisect.bisect_left and the pointer r is calculated by bisect.bisect_right. It is very important to understand how the bisect library works because it is a very useful tool in Python for coding interview.

Implementation

To find l, we start by initializing the low and high pointer:

lo = 0
hi = len(a) - 1

In doing so, we have divided the list into three parts:

  1. a[:lo];
  2. a[lo:hi];
  3. a[hi:].

We maintain the following assertion throughout the algorithm:

  1. all(c < x for c in a[:lo])
  2. all(c >= x for c in a[hi:])

The idea is to shorten a[lo:hi] repeatedly while maintaining the above assertions until it becomes an empty list. Here is when bisection comes in. At the start of every iteration, we take a look at the middle element a[m] of a[lo:hi], where m = (lo+hi)//2. There are two cases:

  1. a[m] < x: in this case, since the list is sorted, we can conclude that every element in a[:m+1] is less than x. Thus, we can safely increase the pointer lo to m+1 without violating the first assertion.
  2. a[m] >= x: every element in a[m:] is greater or equal to x. Thus, we can safely decrease hi to m without violating the second assertion. The above procedure is repeated until a[lo:hi] is empty, i.e. lo == hi. Now we have all(c < x for c in a[:lo]) == True and all(c >= x for c in a[lo:]) == True. It is obvious that now we have l == lo == hi.

Note that it is not essential to let m=(lo+hi)//2. In fact, m can be taken to point to any element in a[lo:hi], that is, m could any integer in range(lo:hi). It is just that letting m be the middle of a[lo:hi] ensures that the length of a[lo:hi] is halved at every iteration.

The following implements the above procedure:

def bisect_left(a, x):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        m = (lo + hi) // 2
        if a[m] < x:
            lo = m + 1
        else:
            hi = m
    return lo

Similarly, the following gives the r pointer:

def bisect_right(a, x):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        m = (lo + hi) // 2
        if a[m] <= x:
            lo = m + 1
        else:
            hi = m
    return lo

Conclusion

To conclude, we have defined a version of binary search (or bisection) that removes the worry of edge cases. That is achieved by forgoing the aim of finding the target element and focusing on dividing the list into three parts, each containing elements that are <, == and > the target element. Edge cases are automatically handled because the middle partition could be of any length. If the middle partition is empty, that means the target element does not exist in the list.