Week 2: Binary Search

In a sorted list, binary search is a good method to search for an item. Each time we pick a “middle element”, and compare it to our target. If it is smaller than the target, then we keep doing binary search on its right side; if it is larger than the target, then we keep doing binary search on its left side. Note that each time we can get rid of about half of the list, so eventually it is an O(\log n) algorithm. If you encounter an interview question asking you to implement an O(\log n) algorithm, most likely it is asking for a binary search. Let’s start from the most classical question on binary search:

Classical Binary Search Question:

Take a look at LeetCode #704:

LeetCode #704. Binary Search

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.


Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

Note:

  1. You may assume that all elements in nums are unique.
  2. n will be in the range [1, 10000].
  3. The value of each element in nums will be in the range [-9999, 9999].

In this case, using the classical version of binary search is perfectly fine:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        start = 0
        end = len(nums) - 1
        found = False
        
        while start <= end and not found:
            mid = (start + end) // 2
            if nums[mid] == target:
                return mid
            else:
                if target < nums[mid]:
                    end = mid - 1
                else:
                    start = mid + 1
        
        return -1

However, for other types of questions, this version of binary search might not work. For example, let’s take a look at the next question:

When Classical Version doesn’t work:

Take a look at Leetcode #34:

LeetCode #34. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given targetvalue.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

Very likely your first attempt would fail, and it is extremely frustrating to debug. The while loop can easily become an infinite loop, and that will give you a “Time Limit Exceeded” error. To fix this, let’s use the following template.

A Better Binary Search Template:

This template code comes from here. Let’s see what is different:

class Solution:
    # @param nums: The integer array
    # @param target: Target number to find
    # @return the first position of target in nums, position start from 0 
    def binarySearch(self, nums, target):
        if len(nums) == 0:
            return -1           

        start, end = 0, len(nums) - 1
        
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[mid] < target:
                start = mid
            elif nums[mid] == target:
                end = mid
            else: 
                end = mid
                
        if nums[start] == target:
            return start
        if nums[end] == target:
            return end
        
        return -1

There are two major points that make this code a nice template:

1. We want to use while start + 1 < end for the while loop. This is because start < end and start <= end may give us infinite loop when finding the last position of target. Consider the following case:

Input: nums = [1, 1], target = 1 Output: [0,1]

If we write start < end, note that here we will have start = 0 all the time as the loop goes. This makes while start < end or while start <= end always evaluate to True, and thus gives us an infinite loop. Using while start + 1 < end helps to get rid of any potential error.

2. We want to use start = mid and end = mid, instead of start = mid + 1 and end = mid - 1. In some special cases, such as finding the last position of target, when target == nums[mid], we can’t write +1 and -1, for that we may miss some solutions. So for simplicity, just write start = mid and end = mid for any binary search question. This makes the algorithm O(\log(n+1)), which doesn’t make much difference as the standard O(\log n).

Solution to LeetCode #34:

Here is a solution to LeetCode #34 using above template:

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        return [self.first_position(nums, target), self.last_position(nums, target)]
    
    def first_position(self, nums, target):
        if len(nums) == 0:
            return -1           

        start, end = 0, len(nums) - 1
        
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[mid] < target:
                start = mid
            elif nums[mid] == target:
                end = mid
            else: 
                end = mid
                
        if nums[start] == target:
            return start
        elif nums[end] == target:
            return end
        else:
            return -1
        
    def last_position(self, nums, target):
        if len(nums) == 0:
            return -1           

        start, end = 0, len(nums) - 1
        
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[mid] < target:
                start = mid
            elif nums[mid] == target:
                start = mid
            else: 
                end = mid
                
        if nums[end] == target:
            return end
        elif nums[start] == target:
            return start
        else:
            return -1

The only two differences between first_position and last_position:

  1. When nums[mid] == target, first_position sets end = mid and last_position sets start = mid. This is very intuitive. For example, in first_position, you can’t just return mid when you find the target. You should set end to mid, so that you can keep searching the elements before it, just to see if the target occurs anywhere before the element you are looking at. Similar reasoning holds for last_position, too.
  2. After the while loop, first_position checks nums[start] first, and last_position checks nums[end] first, for very obvious reason.

Some Examples:

Using the template, binary search questions can be really easy to solve. For example, consider this question:

LeetCode #162. Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.

Note:

Your solution should be in logarithmic complexity.

Solution:

class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return -1
        if len(nums) == 1:
            return 0
        
        start, end = 0, len(nums) - 1
        
        while start + 1 < end:
            mid = (start + end) // 2
            if nums[mid] > nums[mid + 1]:
                end = mid
            else:
                start = mid
                
        if nums[start] > nums[end]:
            return start
        elif nums[start] < nums[end]:
            return end
        else:
            return -1

LeetCode Time!

Let’s Do all problems in this page:
https://leetcode.com/explore/learn/card/binary-search/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s