Binary search is quite easy to understand conceptually, you split the search space into two halves and only keep the half which has the target in it and throw away the other half.

But when it comes to implementation, it is rather difficult to write a bug-free binary search in just a few minutes. Some of the most important questions we ask are:

• When do we exit the loop? Should we use left < right or left <= right in the loop?
• How do we initialise the boundary variables left and right?
• How do we update the boundaries? Do we use left = mid or left = mid + 1?

When I first studied binary search in university I thought binary search could only be used to find simple values in arrays (I also thought that you ate oranges with the skin on them, we live and we learn 🍊)

However, binary search can be applied to many Leetcode hard problems and is extremely useful.

Generalised Binary Search

Suppose we have a search space (whether it be an array, a range of numbers) thats sorted in ascending order.

The following code is the most generalised version of binary search across this search space:

def binary_search(array) -> int:
    def condition(value) -> bool:
    	# The condition depends on what the question is asking us, this should pass True if it is what we're looking for
        pass

    left, right = min(search_space), max(search_space) # Left and right depends on the question. It could be [0, n] or [1, n]
    while left < right:
    	# We do left < right here for a generalised form, we might want an <= depending on the question. Will talk morea bout it later
        mid = left + (right - left) // 2
        if condition(mid):
            right = mid
        else:
            left = mid + 1
    return left

With this template, for most problems, we only really need to modify three parts after copying and pasting it and we never need to worry about corner cases and bugs in code.

1. Correctly initialise the boundary values left and right to specify search space. We need to set up the boundary to include all possible elements.
2. Decide our return value. Do we return left or return left - 1? After exiting the loop, left is the minimal k satisfying the condition.
3. We need to design the condition function. This is the most difficult part and the one you will practice the most ⚒️

Lets run through some simple binary search problems.

First Bad Version

This is a Leetcode easy problem solvable with binary search:

Ghost Admin

Ghost

69.Sqrt(x)

69. Sqrt(x)

Problem Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well. You must not use any built-in exponent function or operator. * For example, do not use pow(x, 0.5) in c++ or x ** 0.

Skerritt.blogBee Skerritt

35.Search Insert Position

35. Search Insert Position

Problem Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity. Example 1: Input: nums

Skerritt.blogAutumn Skerritt

Advanced Applications

The above problems are easy to solve because we are given the search space already and asked to search it.

For more advanced applications we may not even realise we can use Binary Search. Generally if we can discover some kind of statement like if condition(k) is True then condition(k+1) is True then we can consider Binary Search.