From Zero to Binary Search Hero: How to Solve Any Binary Search Problem : Part — 1

Binary search is one of the most important and efficient algorithms you’ll need to master for coding interviews, especially when dealing with sorted arrays. In this guide, I’ll walk you through the essentials of binary search, cover common variations, and equip you with the tools to solve any binary search problem confidently.

What Is Binary Search and Why Does It Matter?

Imagine you’re flipping through a phone book to find a name. Instead of looking at each name one by one, you can go straight to the middle, check if the name is earlier or later in the alphabet, and then halve your search space. This is binary search in action — it eliminates half of the search space each time! It is quite natural for anyone given a dictionary will do that, but applying binary search in some of the computer problems requires some practice.

Binary search is faster than a linear search, with a time complexity of O(log n). This makes it ideal for searching large, sorted datasets. Let’s dive into how to implement it.

Step 1: The Basic Template for Binary Search

Here’s a simple template to start with. The idea is to maintain a search window and shrink it iteratively by adjusting the middle point.

def binarySearch(nums: List[int], target: int) -> int:
    # st(start) points to first elem index, end points to last elem index
    st, end = 0, len(nums) - 1
    while st <= end:
        # Get middle element
        mid = st + (end - st)//2
        # Check condition for the middle element
        if nums[mid] == target:
            # return true if matches the middle
            return mid
        # Move to right if the condition if all the elements to left the middle can be skipped
        if nums[mid] < target:
            st = mid + 1
        else:
        # Else move to the right if all the elements to right of the middle can be skipped.
            end = mid - 1
    return -1

How It Works:

1. Initial Setup: We define start and end to track the current window of interest.

2. Midpoint Calculation: We calculate the midpoint of the array by using mid = start + (end — start) // 2. It is basically (start + end)//2 written in a way which doesn’t overflow.

3. Comparison: If the middle element matches the target, we return its index. If not, we adjust the start or end to narrow down the search space.

4. Return -1: If the target is not found, we return -1.

The above template finds the element if it is present in the sorted array. Although the more interesting case is when the element is not found in the array. As we can see when that happens the function returns -1. But where does start and end point to before the function exists? Is there something we can learn from that.

Let’s take an example:

Input : nums = [1, 5, 10, 12, 15, 19] , target = 13

Iteration 1 : nums = [1, 5, 10, 12, 15, 19] st = 0, end = 5 , mid = 0 + (5 — 0)//2 => 2, nums[mid] = 10 < 13, st = mid + 1 => 3

Iteration 2: nums = [1, 5, 10, 12, 15, 19] st = 3, end = 5 , mid = 3 + (5 — 3)//2 => 4, nums[mid] = 15 > 13, end= mid — 1 => 3

Iteration 3: nums = [1, 5, 10, 12, 15, 19] st = 3, end = 3, mid = 3 + (3–3)//2 => 3, nums[mid] = 12< 13, st= mid +1 => 4 End of iteration as st = 4 > end = 3

As in this example we can see start will be 1 greater than end i.e. start = end + 1, in fact that is what while condition also says while st ≤ end, so it will continue till that happens.

Insight!

The insightful part of the above code is where start and end cross if the number is not found in the array. It can be inferred that the point where start and end will cross will partition the array into two parts lower = [:end] (end is also included) and higher = [start:] (start also included). All the elements if any in lower will be smaller than the target and all the elements in higher if any will be greater than the target. In the above example also you can see nums[:3] => [1, 5, 10, 12] are smaller than target 13 and nums[4:] => [15, 19] are greater than target 13.

Keeping that in mind, binary search code can be thought of partitioning the array such that all the elements to the left of the partition belongs to one category (less than) and elements to the right belong to another category (greater than). And element at end is last element of that category and the element at st is the first element of the other category.

It is upto the problem solver to define these categories based on the problem, and we will see examples. For example in vanilla binary search if the left category is less than target, right category is greater than or equalto the target then at end of the loop startwill point to the target if present and not returned earlier. If target not present than it will be the next higher element than the target.

Out of bounds error is also usually the concern with these problems, and as it can be seen in the binary search if all the elements are lower than the target value then the partition boundary will be at the right end of the array, which can be quickly check if start is still less than the length of the array before return element at index start.

The previous code template, can be transformed based on discussion and also to make reusable for other problems also:

Step 2: The Improvised Binary Search Template

def binarySearch(nums: List[int], target: int) -> int:
    st, end = 0, len(nums) - 1
    while st <= end:
        mid = st + (end - st)//2
        if nums[mid] < target: # If in left parition, move the start to the right
            st = mid + 1
        else: # If in the right parition, move the end to the left
            end = mid - 1
    if st < len(nums) and nums[st] == target:
        return st
    return -1

Now let’s see how binary search is applied to some of the leet code problems:

• First-bad-version

In this problem as can be see the partition can be done into two categories good versions followed by bad versions.

As discussed above thinking of the problem in terms of partitions rather help to use the above template. Idea is to let the while loop run till the start and end crosses each other. When this happens, lets understand what does start and end represents.

• The position of start will the first element on the right partition i.e. first bad version.
• End will point to the last element in the left partition i.e. last good version.

The diagram below shows the end of the while loop.

def firstBadVersion(n: int) -> int:
    st, end = 1, n
    while st <= end:
        mid = st + (end - st)// 2
        isBad = isBadVersion(mid)
        if isBad: # Belongs to right partition, look to the left by moving end to mid - 1
            end = mid - 1
        else: # Belongs to the left partition, look to the right by moving start to mid + 1 
            st = mid + 1
    return st # return the first bad version.

Other similar easy problems you can try:

• https://leetcode.com/problems/search-insert-position
• find-smallest-letter-greater-than-target

Now let’s take it further, until now we look at two categories and finding one partition separating those categories. Now if we increase the category to more than two, thus finding two partitions between categories.

Let’s look at this problem:

• find-first-and-last-position-of-element-in-sorted-array

This problem does binary search to find the target, but if there are multiple targets then need to return the index of first and last target.

This can be interpreted as finding two partition boundaries i.e.

1. Partition/Boundary 1: Left partition contains all element < target and right partition >= target. In that case the start points to index at the end of the loop to the start of =target partition if valid.
2. Partition/Boundary 2: Left partition contains all element <= target and right partition > target. In that case the end points to index at the end of the while loop to the end of =target partition.

So basically we can run binary search twice by defining separate conditions.

def searchRange(nums: List[int], target: int) -> List[int]:
    st , end = 0, len(nums) - 1
    while st <= end: # Find partition 1 boundary 1
        mid = st + (end - st)//2
        if nums[mid] < target:
            st = mid + 1
        else:
            end = mid - 1
    if st == len(nums) or nums[st] != target: # If the target is not found
    # Reached end of array as all numbers were smaller than target.
    # Array doesn't have the target number
        return [-1, -1]
    first, end = st, len(nums) - 1
    while st <= end: # Find partition 2 boundary 2
        mid = st + (end - st)//2
        if nums[mid] <= target:
            st = mid + 1
        else:
            end = mid - 1
    return [first, end]

Other similar problem:

• check-if-a-number-is-majority-element-in-a-sorted-array

Conclusion:

In this article I have covered a basic template for solving binary search interview problems. In the next article will cover some medium and hard problems using the same template.

If you like the article, please subscribe. I am planning to post more articles related to coding interview problems and would love to hear your feedback. You can also follow be on my blog http://adityabhatia.com