Binary Search Cheat Sheet

7 min readJan 30, 2024

Hello! Here I am with yet another update on my journey in strengthening my CS background. So far I’ve covered Pointers, Time Complexity Analysis, and Recursion. In this blog, I am sharing my learnings on Binary Search, inspired by this comprehensive Youtube playlist.

I hope you find the following summary incredibly useful and, as always, please feel free to export the attached cheat sheet :)

What is Binary Search?

Binary Search: an algorithm used to search for an element in a sorted array. It operates by dividing the search space in half in each iteration until either the element is found or the search space is empty.

Objective: Given a sorted array, arr, does x exist?

Note: The property that the array is sorted is a precondition of binary search.

Why use Binary Search?

Efficiency: offers logarithmic time complexity, O(log(n)), ensuring quick searches for large datasets

Minimal Comparison: minimizes comparisons by eliminating half the search space with each iteration

Versatility: can be adapted for various tasks, including finding first or last occurrences, counting elements, etc.

Binary Search Implementation

Steps:

Initialize Pointers: Set low and high pointers to the start and end of the current search space
Middle Element: Identify the middle element, mid, of the current search space; mid is typically found by calculating (low + high) // 2
Comparison: Compare the target x with mid. If equal, search complete. If x is less than mid, narrow the search space to the left half. If x is greater than mid, narrow the search space to the right half.
Repeat: Continue until x is found or the search space is empty.

Now, let’s see this in action. Using the same sorted array as previously mentioned, we’ll use binary search to find 13. Our first step involves setting low and high to the array’s start (index 0) and end (index 8) respectively. Subsequently, we calculate the midpoint, which yields mid as (low + high) // 2 = (0 + 8) // 2 = 4.

Next, we evaluate x (13) against the value stored at the mid. Since 13 is smaller than 36, and considering the sorted nature of the array, we know that there’s a chance 13 might exist in the lower half. Consequently, this narrows our search space in half by discarding the upper half.

After eliminating the upper half, we reset low and high to the current search space’s start (index 0) and end (index 3) and recalculate mid.

This time 13 is larger than 6, which means that there’s a chance 13 exists in the upper half. As a result, we eliminate the lower half, and repeat the process of resetting low and high and recalculating mid.

In this final iteration, we find 13 to be at the mid which puts an end to our search :)

Binary Code Search Snippet (Python)

Below is a binary search solution written in Python,

def binary_search(arr, x):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == x:
            return mid # x is found
        elif arr[mid] < x:
            low = mid + 1  # Modify low to search upper half
        else: 
            high = mid - 1  # Modify high to search lower half
    return -1 # x not found

Linear Search vs Binary Search

Linear Search: involves scanning through the array sequentially, starting from the beginning until the target x is located. In the best-case scenario, x is found at the array’s initial index, while in the worst case, x is situated at the array’s end. Some other characteristics include:

Applicable to unsorted arrays
Simple but less efficient for large datasets
Linear time complexity (O(n))

Binary Search:

Requires sorted array
More efficient for large datasets
Logarithmic time complexity (O(log(n)))

Binary Search with Recursion

A recursive solution can be written for binary search,

def binary_search(arr, x, low, high):
    if low <= high:
        mid = (low + high) // 2
        if arr[mid] == x:
            return mid # x is found
        elif arr[mid] < x:
            return binary_search(arr,
                                 x,
                                 mid + 1,  # Modify low to search upper half
                                 high)
        else:
            return binary_search(arr,
                                 x,
                                 low,
                                 mid + 1)  # Modify high to search lower half
    return -1 # x not found

Advantages:

Elegant Solution: Concise and easy to understand
Same Time Complexity: Logarithmic (O(log(n)))

Finding First or Last Occurrence

Objective: We can modify binary search to find the first or last occurrence of target x in a sorted array.

Approach:

Finding first occurrence: If x found, continue searching in the lower half for an earlier occurrence.

Let’s say we want to find the first occurrence of 5. To begin, we would follow the usual steps of binary search and set low and high, and calculate mid. In this first iteration, we find that mid is equal to our target 5, but we don’t know for certain this is the first occurrence. For now, we’ll save the index in a variable called result.

Because we want to find the first occurrence, we narrow our search space to the lower half. Again, we reset low and high and recalculate mid.

We compare our target, 5, to the value stored at mid. Because 5 is greater than 1, we will narrow our search to the upper half and reset low and high and recalculate mid accordingly.

We perform another comparison of our target, 5, with the value stored at mid. Because 5 is greater than 3, we will narrow our search to the upper half and reset low and high and recalculate mid accordingly.

This time we found our target, 5, to be equal to the value stored at mid, indicating an earlier occurrence. We overwrite the value stored in result with the index, and because our search space is empty after this iteration, we can confidently say that we found the first occurrence of 5 to be at index 3 :)

Finding last occurrence: Finding the last occurrence of x is similar to the process of finding the first occurrence. Instead of continuing to search in the lower half, we search in the upper half for a later occurrence.

I won’t walk you through an example given its similarity to finding the first occurrence, hopefully you understand the full picture :)

Code Snippet (Python)

def binary_search(arr, x, search_first):
    low, high, result = 0, len(arr) - 1, -1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == x:
            result = mid
            if search_first:
                # Modify high to search lower half for earlier occurrence
                high = mid - 1  
            else:
                # Modify low to search upper half for later occurrence
                low = mid + 1  
        elif arr[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return result

Count of an Element

Objective: We can also leverage binary search to determine the count of x in a sorted array

Approach:

Use binary search to find the first occurrence
Use binary search to find the last occurrence
Count calculation = last occurrence — first occurrence + 1

Code Snippet (Python)

def count_occurrences(arr, x):
    # using search_first parameter
    first_occurrence = binary_search(arr,
                                     x,
                                     True)
    last_occurrence = binary_search(arr,
                                    x,
                                    False)
    if first_occurrence = -1:
        return 0 # x not found
    else:
        return last_occurrence - first_occurrence + 1