Binary Search: Boundary Handling

1. The Core Idea: Divide and Conquer

Binary search operates on a simple "divide and conquer" principle. If you're looking for an item in a sorted list, you can eliminate half of the remaining items in a single step. Think of finding a name in a phone book or a word in a dictionary. You don't start from page one; you open it to the middle, see if your word comes before or after that page, and then repeat the process on the relevant half.

In an array, this translates to:

1. Start with a search space covering the entire array, defined by left and right pointers.
2. Check the element at the middle index, mid.
3. If nums[mid] is the target, you're done!
4. If nums[mid] is less than the target, you know the target must be in the right half. You can discard the entire left half.
5. If nums[mid] is greater than the target, the target must be in the left half. You can discard the entire right half.
6. Repeat this process on the smaller search space until you find the target or the search space is empty.

Let's watch a quick video that walks through this core concept.

The power of this approach lies in its logarithmic time complexity, O(log n). By halving the search space each time, the number of operations grows very slowly as the array size n increases. For an array with a million elements, a linear search might take a million steps, while binary search would take at most 20.

2. Building a Bulletproof Implementation

While the concept is simple, implementing binary search correctly is notoriously tricky. Off-by-one errors in pointer initialization, loop conditions, or midpoint calculations can lead to infinite loops or incorrect results on edge cases.

We are going to build a robust, standard template by examining a buggy implementation and fixing it step-by-step. This process will highlight the critical details you must get right. The following article provides a perfect walkthrough of these common pitfalls.

Let's synthesize those fixes into a standard, reliable template in Python. This is the version you should aim to master.

def binary_search(nums, target):
    # 1. Initialize pointers for the search space [0, n-1]
    left, right = 0, len(nums) - 1

    # 2. Loop while the search space is valid (left <= right)
    while left <= right:
        # 3. Calculate mid-point safely to avoid overflow
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            # 4a. Target is in the right half, discard the left half
            # We can also discard 'mid' itself
            left = mid + 1
        else: # nums[mid] > target
            # 4b. Target is in the left half, discard the right half
            # We can also discard 'mid' itself
            right = mid - 1

    # 5. If the loop finishes, the target was not found
    return -1

Let's break down the key decisions in this template:

1. right = len(nums) - 1: Your search space [left, right] should be inclusive of all valid indices.
2. while left <= right: The <= is crucial. It ensures that the loop runs even when the search space has been narrowed to a single element (left == right). If we used <, we would exit the loop without checking that last element.
3. mid = left + (right - left) // 2: As the article noted, this prevents potential integer overflow in languages like Java or C++ when left and right are very large. While Python handles arbitrarily large integers, this is a universal best practice that interviewers appreciate.
4. left = mid + 1 and right = mid - 1: Since we've already checked nums[mid] and it wasn't the target, we can exclude it from the next search space. This is essential for guaranteeing the loop terminates and avoids infinite loops.

This exact implementation is also demonstrated in the NeetCode video you saw earlier. Watching the code-through will help connect all these pieces.

3. Variations and Boundary Handling

The template we've learned is for the most common case: finding an exact value. You might see other templates online that use while left < right or update pointers to right = mid. These are not necessarily wrong; they are simply designed for different search interval definitions ([inclusive, exclusive]) and are often used in more advanced binary search problems.

This short video brilliantly explains the trade-offs.

The key takeaway is that for standard search problems, the while left <= right template is generally safer and easier to reason about. We will explore other templates in later lessons when we tackle problems that require finding the first/last occurrence of an element or searching for an optimal value.

Conclusion

Excellent job! You've not only learned the theory of binary search but have also built a robust, interview-ready implementation by understanding the common pitfalls.

Key Takeaways:

• Efficiency: Binary search provides O(log n) time complexity for searching in sorted arrays, a significant improvement over O(n) linear search.
• Robust Template: For finding a specific element, stick to this template:
  • Initialize left, right = 0, len(nums) - 1.
  • Loop with while left <= right.
  • Calculate mid = left + (right - left) // 2.
  • Shrink the search space with left = mid + 1 or right = mid - 1.
• Boundary Handling is Key: Small off-by-one errors can break the algorithm. Understanding why each part of the template exists is crucial for debugging and adapting it later.

In our next lesson, we will build on this foundation. You'll apply this core binary search skill to solve more complex interview problems, such as finding the insertion position for a new element or finding the start and end indices of a target that appears multiple times in an array.