Binary Search on Sorted Arrays

The Problem with Linear Search

Imagine you're looking for a specific number in a large, unsorted list. The only way to guarantee you find it is to check every single element, one by one, from the beginning to the end. This is called a linear search. For a list with n elements, this could take up to n comparisons in the worst case. If your list has a billion items, that's a billion checks!

Binary Search: A "Divide and Conquer" Strategy

Now, what if the list was sorted? Think about looking up a word in a physical dictionary. You don't start from the first page. You open it somewhere in the middle. If the word you see comes after your target word, you know your word must be in the first half. If it comes before, you know your word is in the second half. You've just eliminated half the dictionary in a single step.

This is the core idea of binary search. It's a "divide and conquer" algorithm that works on sorted data. By repeatedly dividing the search space in half, it can find a target element with remarkable speed.

Let's watch a video that visualizes this process.

As you saw, the algorithm maintains a search space using two pointers, typically called left and right.

1. Calculate the middle index, mid.
2. Compare the element at mid with your target.
3. If it's a match, you're done!
4. If the middle element is less than the target, you know the target must be in the right half, so you move your left pointer to mid + 1.
5. If the middle element is greater than the target, the target must be in the left half, so you move your right pointer to mid - 1.
6. You repeat this until you find the element or the search space becomes empty (left crosses right).

Here's a static image that breaks down the process step-by-step.

Implementing Binary Search in Python

Now that you understand the concept, let's translate it into code. The most common way to implement binary search is with an iterative approach using a while loop.

This next video segment walks through a complete Python implementation.

Here's the code structure we just saw:

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

    while left <= right:
        # Calculate the middle index
        mid = (left + right) // 2  # Using // for integer division

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

    return -1 # Target not found

A Note on Calculating the Midpoint

The calculation mid = (left + right) // 2 is simple and works perfectly fine in Python, because Python's integers can grow to any size needed.

However, in other languages like C++ or Java, where integers have a fixed size (e.g., 32-bit or 64-bit), left + right could potentially exceed the maximum integer value, causing an integer overflow and leading to an incorrect mid value. This is a classic interview question.

A safer way to calculate the midpoint, which avoids overflow, is:
mid = left + (right - left) // 2

Let's watch a brief explanation of this.

While you don't have to use this safer formula in Python for LeetCode-style problems, being aware of it demonstrates a deeper understanding of potential programming pitfalls.

Complexity Analysis: The Power of Logarithms

Why is binary search so fast? Each time we make a comparison, we cut the search space in half.

• If we start with n elements, after 1 step we have n/2 elements left.
• After 2 steps, we have n/4.
• After k steps, we have n / 2^k elements.

The algorithm stops when we have only one element left, i.e., when n / 2^k = 1. Solving for k gives us 2^k = n, which means k = log₂(n). This means the number of steps grows logarithmically with the size of the array, giving us a time complexity of O(log n).

The iterative implementation uses only a few variables (left, right, mid), so its space complexity is O(1) (constant space).

Consolidation and Further Reading

To solidify your understanding, please read the following article. It provides a great summary of what we've covered and also shows a recursive implementation, which is another way to think about the problem.

Conclusion

Congratulations on learning your first major search algorithm! It is a fundamental building block for more complex problems and data structures.

Key Takeaways:

• Binary search is a highly efficient algorithm for finding an element in a sorted array.
• It works by repeatedly dividing the search space in half, a strategy known as "divide and conquer".
• The standard iterative implementation uses left and right pointers and a while loop.
• Its time complexity is O(log n), a massive improvement over the O(n) of linear search.
• The iterative version has a space complexity of O(1).

Up Next:

Finding an element in a sorted array is just the beginning. The true power of binary search comes from applying it to more abstract problems. In our next lesson, we will explore how to apply binary search to find solutions in a monotonic search space. This technique allows you to solve problems that might not look like searching problems at first glance.