Binary Search Explained

7 min readMay 21, 2023

Let’s learn about another sorting algorithm, Binary Search. Now, this sorting algorithm is actually something our brains use everyday. First, let’s review Linear Search. It is a simple algorithm for finding a specific item in an unsorted list by checking each element in the list one-by-one. Searching for a specific item in a list, one-by-one, takes much more time and computing power. NOTE: It can only work on data that is sorted, usually in increasing order.

Overview

Binary Search is an efficient algorithm for finding a specific item in a sorted list by repeatedly dividing the search interval in half.

Imagine you’re playing a game where someone has hidden a letter of the alphabet in a list of letters, and you have to find it by guessing. The person who hid the letter tells you “hotter” or “colder” depending on whether you’re getting closer or farther away from the letter. If we use binary search, we can eliminate half of the wrong answers every iteration until we either reach our target or figure out that the value doesn’t exist in the given list.

Why should I use Binary Search?

You should use binary search when you need to search for a specific item in a large and sorted list because it’s a highly efficient algorithm that can quickly locate the desired item by repeatedly dividing the search space in half. Compared to linear search, which checks every element in the list one by one, binary search can significantly reduce the number of comparisons needed to find the item, especially for larger lists. This makes binary search an ideal choice for performance-critical applications, where speed and efficiency are crucial.

Big-O Analysis

In this article, the concept of reducing the time utilized and number of comparisons when searching is a big deal. I’ve mentioned linear time, but I think it is actually very helpful visualize the various functions that represent time complexity.

Time Complexity

Time complexity is a mathematical approximation. An algorithm’s time complexity approximates its worst case run time. Note that binary search has a linear or constant time complexity, which is denoted as O(log n). This value is illustrated in black below.

*Lines made with the very excellent Desmos graph calculator. You can* *play with this graph here*. *Image credit*.

Let’s visualize this concept before diving into the details by playing a simple guessing game. Imagine you’re playing a game where someone has hidden a letter of the alphabet in a list of letters, and you have to find it by guessing. The person who hid the letter tells you “hotter” or “colder” depending on whether you’re getting closer or farther away from the letter.

Now, let’s say you have a sorted list of letters from “a" to "h," and you're looking for the letter "f." You could start at the beginning of the list and search one letter at a time, but that would take a long time. Instead, you can use binary search to make it faster and more efficient.

Here’s how it works: you start by looking at the middle letter in the list, which is “d." You compare it to your target letter, "f." If "d" comes before "f" in the alphabet, you know the target letter must be in the second half of the list. So you discard the first half of the list and focus on the second half.

Now, you repeat the process with the new, smaller list.

You look at the middle letter, which is “f," and compare it to your target letter, also "f." You've found your target letter!

You keep dividing the remaining list in half and comparing the middle letter to your target letter until you either find the letter “f" or determine that it's not in the list.

This is an example of a “divide and conquer” algorithm because you divide the search space (the list) into smaller and smaller parts until you find what you’re looking for. And just like in the “hot and cold” game, each time you eliminate half of the remaining possibilities, you’re getting “hotter” and closer to your target.

So, binary search is a “divide and conquer” algorithm that uses the “hot and cold” reference to quickly find a specific item in a sorted list of items by repeatedly dividing the search interval in half.

Let’s run through an example

Let’s attempt Leetcode problem 704. Binary Search. In this problem, we are given a sorted array of integers nums which goes from smallest to largest number. We are asked to write an algorithm which searches for a targetand returns either the index the element resides at or -1 if no match is found.

We will use the first example:

nums = [-1,0,3,5,9,12], target = 9

To apply the binary search algorithm, let’s first write out the pseudo code in steps to understand the bird’s eye view.

Pseudocode

def binary_search(self, nums, target):
  # create two points for either end of the sorted array `nums`
  # iterate over the array
    # find the current midpoint
    # check if the midpoint is bigger than target
    # if else the midpoint is smaller than target
    # otherwise, we have a match
  # if after all iterations, no matech is found, return -1

So, if we put that information to use we can label the first index and last index as our l and r pointers.

We will be looping over this array every time we do a lookup. Therefore, inside the loop we can assign the mid-point since this value will be updated each iteration.

You can either choose to have a lower bounded mid-point or an upper bounded mid-point. Keep in mind that there may be different edge cases to consider. For this problem, to avoid an edge case, I will use floor division to isolate the mid-point.

This is the first iteration where we will checking whether or not the midpoint is equal to the target we are looking for. In the case that the target value is either greater OR equal to or less than the midpoint, we need to update the corresponding pointers. Finally, we can check if the midpoint is a match for the target, if so we return that index. Otherwise, we return the value -1. Below is an animation to illustrate this example:

Code Implementation

def search(self, nums: List[int], target: int) -> int:
        # create two points for either end of the sorted array `nums`
        l, r = 0, len(nums) - 1
        
        # iterate over the array
        while l <= r:
            m = l + ((r-l) // 2) # floor division

            # check if the midpoint is bigger than target
            if nums[m] > target:
                # update RHS
                r = m - 1
            # midpoint is smaller than target
            elif nums[m] < target:
                l = m + 1
            # match is found
            else:
                return m
        # no match found
        return -1

When should I use this algorithm?

You would want to use binary search for any of the following scenarios below (remember that binary search has a time complexity of O(log n)):

Sorted data: Binary search works best on sorted data.
Efficiency: Binary search offers faster searching for large datasets.
Random access: Binary search requires direct access to elements.
Elimination-based search: Binary search eliminates half of the search space in each iteration.
Infrequent modifications: Binary search is most suitable for static or infrequently changing data.
If the problem statement wants a solution that has time complexity of O(log n), this may be a hint to use Binary Search.