Binary Search All in One

[Glad to hear that this article helped my friend and he solved a binary search problem quickly and accurately during a TikTok interview.]

Even though there are many different types of binary search scenarios, almost every binary search problem can be reduced to the following paradigm:

• The whole array can be split into two parts (left and right).
• Left part complies with rule R
• Right part complies with rule $ \neg R $
• We need to find the first element of the second part, or the last element of the first part.

The pseudo code for solving this problem can be:

def binary_search(nums):
  	length = len(nums)
    l, r = 0, length - 1
    while l <= r:
      	mid = (l + r) >> 1
        if R(nums[mid]):
          	l = mid + 1
        else:
          	r = mid - 1
    # return l if we are looking for the first element of the right part
    # return r if we are looking for the last element of the left part

To elaborate on this piece of code:

1. l, r are the endpoints of the array
2. $ mid = (l + r) // 2 $ (find the middle point of the range [l, r])
3. if mid falls in the left part (follows rule R): the objective we are looking for is on the right side of mid, so $ l = mid + 1 $
4. else: objective is on the left side, $ r = mid - 1 $

When the loop ends, it is guaranteed that $ l == r + 1 $, and $ l $ will be the first element of the right part, $ r $ will be the last element of the last part.

Note that in some test cases, the left or right part might not exist, i.e., their length is 0. There should be some special handles when the index is out of range

Lets take several examples:

852. Peak Index in a Mountain Array

You are given an integer mountain array arr of length n where the values increase to a peak element and then decrease.

Return the index of the peak element.

Your task is to solve it in O(log(n)) time complexity.

The array can be split into two parts:

• left (uphill): $ arr[i] > arr[i - 1] $
• right (downhill): $ arr[i] < arr[i - 1] $

The peak element we are looking for is the last element of left part. Hence the code is:

class Solution:
    def peakIndexInMountainArray(self, arr: List[int]) -> int:
        # find the first element that < its previous element
        l = 0
        r = len(arr) - 1
        while l <= r:
            mid = (l + r) >> 1
            if mid > 0 and arr[mid] > arr[mid - 1]:
                l = mid + 1
            else:
                r = mid - 1
        return r

33. Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly left rotated at an unknown index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be left rotated by 3 indices and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

The array can be split into two parts.

• left: arr[i] >= arr[0]
• right: arr[i] < arr[0]

The approach is to first find out the boundary of these two parts, determine which part the target might belong to, and find if it exists in that part.

The boundary actually falls between the last element of the left part and the first element of the right part, but we can take it this way: the right boundary of the left part is its last element, and the left boundary of the right part is its first element.

After finding the boundary, we can determine the left part and right part. In each part, elements are strictly increasing. We can use another binary search to find out if the target is among one of them.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        length = len(nums)
        l, r = 0, length - 1
        # find the boundary
        while l <= r:
            mid = (l + r) >> 1
            if nums[mid] >= nums[0]:
                l = mid + 1
            else:
                r = mid - 1
        
        # determine which part the target might belongs to, adjust the range for searching accordingly
        if target >= nums[0]:
            l, r = 0, r
        else:
            l, r = l, length - 1
        
        # find the element in that range
        while l <= r:
            mid = (l + r) >> 1
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        
        return -1