Binary Search

By /

Introduction

Binary search is a very popular algorithm for finding a target element in a sorted array.

Algorithm

Here’s a standard way for implementing this algorithm:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return left if nums[left] == target else -1

Time complexity: O(logn). Space complexity: O(1).

However, this implementation will be problematic if we use it to solve other similar questions. Let’s say if we have duplicate elements inside a sorted array and we want to find the last position of a target number, we’ll need to modify the code as following:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] == target:
                left = mid
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        
        return left if nums[left] == target else -1

Note we changed the code at line 10. However, this code will result in a dead loop. Why? Take a look at following simple example:

[1,    1]         target is 1
 ^     ^
start end

In this case, start is at index 0, and end is at index 1. mid = (start + end) / 2 = (0 + 1) /2 = 0. So will be falling into line 10, that left = 0. After we re-enter the loop, left = 0, right = 1 so nothing is changed, and this is a dead loop.

Unfortunately, there’re more such cases need to be dealt with. Sometimes we change the mid index to (start + end + 1) / 2, sometimes we need to change the if clauses inside the loop, such as left = mid, left = mid + 1, left = mid - 1 etc.. What a nightmare! Is there a universal template solution that can be used to resolve everything?

The root cause for these problems is the breaking loop condition. We always assume once left pointer and right pointer pointing to same element and then we exit. If we change the condition to: once the 2 pointers are adjacent to each other, we break out the loop. If the question is asking the last position of element, we check the right pointer. If question is asking the first position, we first check the left pointer, etc.. Thus we don’t need to worry all the problems we talked about before.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        
        left, right = 0, len(nums) - 1
        while left + 1 < right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                left = mid
            else:
                right = mid
        
        if nums[left] == target:
            return left
        
        if nums[right] == target:
            return right
        
        return -1

Though the implementation will be a little bit longer, it saves us from lots of headaches. Also, we no longer need to care whether left or right should be assigned with mid - 1, mid or mid + 1. In this template, it’s always mid.

Summary

4 things to keep in mind in this template:

  • while start + 1 < end, means when start and end indices are adjacent, we exit the loop.
  • Since when start and end indices are adjacent when we exit the loop, we need to check both indices to see which one is the right answer.
  • left = mid or right = mid. No need to think about other cases. But if you know what you’re doing, feel free to ingore this.
  • If you’re using Java: int mid = start + (end - start) / 2 to avoid the sum of start and end exceeds the maximum integer in Java.
Scroll to Top