Binary Search Explained: A Step-by-Step Guide

You’re staring at a list of 10,000 student IDs, sorted by number. You need to find if the ID 2023456 exists. Your first instinct? Start from the top and check each one. That’s a linear search, and it’s painfully slow. If the ID you’re looking for is at the end, you’ve just made 10,000 comparisons.

But what if I told there’s a way to find it in, at most, 14 steps? That’s the power of binary search. It’s one of the first algorithms you learn in computer science, and for a good reason. It’s elegant, incredibly efficient, and a frequent guest in technical interviews and assignments. Let’s break it down so you never have to fear it again.

2. Find the Middle

The next step is to find the middle element between your left and right boundaries. A common and safe way to calculate the middle index is:

mid = left + (right - left) // 2

Why this formula, and not (left + right) // 2? For very large arrays, left + right could exceed the maximum integer value your programming language can hold, causing an integer overflow error. The safer method avoids this issue entirely.

3. Compare and Conquer

Now, compare the value at the mid index with your target value (x). There are three possible outcomes:

• Case 1: arr[mid] == x : You’ve found it! The search is complete. Return the mid index.
• Case 2: arr[mid] > x : The target is smaller than the middle element. This means it must lie in the left half of the current search range. So, you discard the right half by updating your right boundary: right = mid - 1.
• Case 3: arr[mid] < x : The target is larger than the middle element. This means it must lie in the right half. So, you discard the left half: left = mid + 1.

4. Repeat Until Found or Range is Empty

You repeat steps 2 and 3. With each iteration, you cut the search area in half. You continue this loop until one of two things happens:

1. You find the target and return its index.
2. The left boundary becomes greater than the right boundary (left > right). This means your search range is empty, and the target is not in the array.

5. Putting It All Together: The Code

Here’s a classic, iterative implementation of binary search in Python:

def binary_search(arr, target):
    """
    Performs binary search on a sorted array.

    Args:
        arr: A sorted list of elements (e.g., numbers).
        target: The element to search for.

    Returns:
        The index of the target if found, otherwise -1.
    """
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2  # Prevent integer overflow

        if arr[mid] == target:
            return mid  # Target found!
        elif arr[mid] < target:
            left = mid + 1  # Search in the right half
        else:
            right = mid - 1  # Search in the left half

    return -1  # Target not found

# Example Usage
sorted_numbers = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]
target_value = 23

result_index = binary_search(sorted_numbers, target_value)

if result_index != -1:
    print(f"Target {target_value} found at index {result_index}.")
else:
    print(f"Target {target_value} not found in the array.")



Target 23 found at index 5.

Common Mistakes Students Make (And How to Avoid Them)

Even with a simple algorithm, there are a few classic traps that can lead to bugs, infinite loops, or just plain wrong answers. Here’s what to watch out for.

1. The Off-by-One Error in Loop Condition

• What it looks like: Using while left < right instead of while left <= right.
• Why it happens: Students often forget that when left and right become equal, there is still one element left to check. If the loop stops, you’ll miss it.
• How to avoid it: Remember the invariant. As long as your search range is defined by [left, right] (inclusive), you must continue as long as left <= right. Trace through a simple example with a single-element array.

2. Incorrectly Updating Boundaries

• What it looks like: Setting left = mid or right = mid instead of mid + 1 or mid - 1.
• Why it happens: The logic seems sound: “If the target isn’t at mid, let’s search from mid to right.” But since we already know arr[mid] isn’t the target, we should exclude it from the new search range.
• How to avoid it: Always exclude mid. If the target is greater than arr[mid], the new range should start just after mid (mid + 1). If it’s smaller, the new range should end just before mid (mid - 1).

3. Integer Overflow in Mid Calculation

• What it looks like: Using mid = (left + right) // 2 in languages like C++ or Java, which can cause a crash or unexpected behavior for very large arrays.
• Why it happens: The sum left + right might exceed the maximum value an integer can hold, even if each individual variable is within its limit.
• How to avoid it: Always use the safe formula: mid = left + (right - left) // 2. This is a standard best practice, especially in technical interviews.

4. Forgetting the Array Must Be Sorted

• What it looks like: You run binary search on [3, 1, 7, 2, 9] looking for 7. The algorithm might return -1 or, worse, an incorrect index.
• Why it happens: It’s a simple oversight. The power of binary search relies entirely on the sorted order to make its “discard half” decision. If the array isn’t sorted, that decision is meaningless.
• How to avoid it: Check your input! If you’re given an unsorted array, you have two options: sort it first (which takes O(n log n) time) or use a linear search. If you’re writing a function for an assignment, always add a comment or assertion that the input array must be sorted.
  Ready to go deeper? Join our expert sessions and master advanced search techniques.

Beyond the Basics: Variations of Binary Search

Once you’ve mastered the classic search, you’ll encounter problems that require a twist on the standard algorithm. Let’s look at a couple of the most common ones.

Finding the First or Last Occurrence

What if your sorted array has duplicates, like [1, 2, 3, 3, 3, 4, 5], and you need to find the index of the first 3? The standard binary search will return any 3 it finds (probably the middle one), but not necessarily the first.

To find the first occurrence, we modify the logic when arr[mid] == target. Instead of returning immediately, we suspect there might be another target to the left. So, we continue the search on the left half by setting right = mid - 1. However, we need to remember the potential answer. Here’s how it looks:

def find_first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            result = mid      # Record this as a potential answer
            right = mid - 1   # But keep looking for an earlier one on the left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result

Finding the last occurrence is symmetrical: when you find a match, record it and search the right half (left = mid + 1).

Searching in a Rotated Sorted Array

A popular interview question: “Search in a Rotated Sorted Array.” The input is a sorted array that has been rotated at some pivot, e.g., [4, 5, 6, 7, 0, 1, 2]. It’s not fully sorted, but it’s composed of two sorted halves.

The trick is to modify the decision-making process. After calculating mid, you first determine which half (left or right) is normally sorted. Then, you check if the target lies within that sorted half. If it does, you search there; otherwise, you search the other half.

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        # Check if the left half is sorted
        if nums[left] <= nums[mid]:
            # If target is in the sorted left half
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Otherwise, the right half is sorted
        else:
            # If target is in the sorted right half
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

This is a powerful example of how understanding the core principle allows you to adapt it to more complex scenarios.

Frequently Asked Questions (FAQ)

1. Is binary search always faster than linear search?
For small arrays (say, less than 20-30 elements), linear search can be faster due to its simplicity and better cache performance. The overhead of binary search’s calculations might not be worth it. However, as the size of the data grows, binary search’s O(log n) time complexity makes it exponentially faster.

2. What is the time complexity of binary search?
The time complexity is O(log n). This means that with each step, the algorithm halves the search space. For an array of size 1,000, it takes about 10 steps. For size 1,000,000, it takes about 20 steps. Its space complexity is O(1) for the iterative version, as it only uses a few variables.

3. Can I use binary search on a linked list?
Technically, you can perform a binary search on a sorted linked list, but it’s extremely inefficient. Accessing the middle element of a linked list takes O(n) time because you have to traverse from the head. This would make the overall algorithm O(n log n), which is worse than a simple linear scan (O(n)). Binary search is designed for data structures with random access, like arrays.

4. What are lower bound and upper bound in the context of binary search?
These are common variations. The lower bound is the first index where the value is greater than or equal to the target. The upper bound is the first index where the value is strictly greater than the target. These are implemented in C++ as std::lower_bound and std::upper_bound and are crucial for solving many problems. The find_first_occurrence example above is a form of lower bound.

5. What happens if the array has duplicate values?
Standard binary search will return the index of a matching element, but not necessarily the first or last. As we saw in the variations, you need to modify the algorithm slightly to handle duplicates if the position of the first or last occurrence is required.

6. Can I implement binary search recursively?
Yes! The recursive version is often more elegant. The base case is when left > right (not found). Otherwise, you compute mid and then recursively call the function on either the left or right half.

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1

    mid = left + (right - left) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

7. What is the “binary search on answer” concept?
This is an advanced but powerful technique. Instead of searching for a value in an array, you search for an answer within a range of possible answers. For example, finding the square root of a number or the minimum capacity of a ship to deliver packages within a given time. You define a range of possible answers and use binary search to find the smallest (or largest) one that satisfies a condition.

Conclusion

Binary search is more than just an algorithm; it’s a fundamental way of thinking about problem-solving. 

By mastering its classic form and common variations, you’ve equipped yourself with a tool that will save you time in your code, impress your professors, and help you tackle a huge category of technical interview questions. 

Remember the core principles: a sorted array, dividing the search space in half, and carefully managing your boundaries.

If you’re working on a tricky assignment involving search algorithms or just want to build a rock-solid foundation for your coding interviews, don’t struggle alone. Get personalized feedback and guidance from our expert tutors.

Submit your assignment for a detailed code review and get feedback on your binary search implementation.

Book a tutoring session for one-on-one help mastering data structures and algorithms.

Read more articles on our blog to boost your programming skills, like our guides on Two Pointers Technique and Understanding Big-O Notation.