The Ultimate guide of Binary Search

Photo by Marten Newhall on Unsplash

Binary Search is a very useful algorithm where its input is a sorted list of elements. It provides time complexity of O(logN) which can largely save the search time.

Why O(logN) ?

The magic behind this efficiency lies in repeatedly dividing the array in half during each iteration, so every time you a call the subroutine ( or complete one iteration ) the size reduced to half of the existing part.

The maximum no of iterations is O(logN) (base 2).

For the most basic Binary Search problem you may have met before, it usually looks like this:

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

And the solution is shown below:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # Set the left and right boundaries
        left = 0
        right = len(nums) - 1
        
        # Under this condition
        while left <= right:
            # Get the middle index and the middle value.
            mid = (left + right) // 2
            
            # Case 1, return the middle index.
            if nums[mid] == target:
                return mid
            # Case 2, discard the smaller half.
            elif nums[mid] < target:
                left = mid + 1                 
            # Case 3, discard the larger half.         
            else:
                right = mid - 1
        
        # If we finish the search without finding target, return -1.
        return -1

However, Binary Search is not always this straightforward, and numerous variations exist. To tackle these more complex problems, here’s a summary of essential tips:

Tips:

1. It’s always better to write mid = left + (right — left) // 2 instead of mid = (left + right) //2 . For detailed research, please have a look of this blog.
2. Watch out the loop condition: while left < right or while left <= right.
3. Be careful when nums[mid] == target , here the target may vary based on the problem requests. It can be a fixed value, a variable like nums[0] or nums[right] , or even neighbours of nums[mid].
4. Pay attention to left and right updates. should it be left = mid or left = mid + 1 ? Should it be right = mid or right = mid - 1 ?
5. Return logic. Usually it can be 2 cases. return left or return mid based on the requests. Sometimes left and mid are the same but sometimes not.
6. After you check all these steps, please take some time to go through your code with corner cases.
   - an array with length 1
   - an array with length 2
   - an array with length 3
   - example arrays in the problem
   If there is any single case which doesn’t work with your code. Think about adding conditional statements before your while loop begins.
7. Binary search can integrate with other approaches like sliding window.

Templates:

The picture below shows 3 types of templates from Leetcode but still my tips above has included all of them.

Binary Search Templates from Leetcode

In summary, Binary Search is a must-know algorithm for efficient problem-solving. By grasping its core principles and applying the tips provided here, you can confidently tackle a variety of challenges. Remember, Binary Search isn’t just a standalone tool; it can enhance your problem-solving abilities when combined with other techniques.

Stay updated with more tech insights by following TechWithPlum. Happy coding!

Just to update, this article is the worst one I have ever written so far as it is not clear enough for binary search guidance. But still, I chose to keep my previous failing article here to reflect my clumsy coding progress. Here I found another super template for binary search from Leetcode, feel free to try this template for tons of binary search problems.

def binary_search(array) -> int:
    def condition(value) -> bool:
        pass

    left, right = min(search_space), max(search_space) # could be [0, n], [1, n] etc. Depends on problem
    while left < right:
        mid = left + (right - left) // 2
        if condition(mid):
            right = mid
        else:
            left = mid + 1
    return left