Modified Binary Search for Rotated Arrays

Welcome to our next lesson. We've spent the last few sessions exploring how heaps can be used to solve complex problems involving dynamic sets of data, like finding a running median. Today, we shift our focus from heap-based patterns to another fundamental algorithmic category: advanced searching.

You are likely very familiar with binary search, the quintessential $O(\log N)$ algorithm for finding an element in a sorted array. But what happens when the array isn't perfectly sorted? In interviews for high-performance systems roles, you'll often encounter problems that test your ability to adapt core algorithms to new constraints. This lesson is dedicated to exactly that. We will explore the Modified Binary Search pattern, learning how to apply it to arrays that are "almost sorted"—specifically, rotated sorted arrays and arrays where elements are slightly displaced.

By the end of this lesson, you will be able to identify and implement efficient logarithmic-time solutions for searching in these non-standard, yet structured, array types.

1. The Challenge: A Sorted Array with a Twist

Standard binary search relies on a simple, powerful invariant: if the target is less than the middle element, it must be in the left half, and if it's greater, it must be in the right half. This invariant breaks the moment the array's perfect order is disrupted.

Consider an array that was sorted and then rotated. For example, [0, 1, 2, 4, 5, 6, 7] rotated by 4 positions becomes [4, 5, 6, 7, 0, 1, 2]. If we search for 0 and pick a midpoint, say 7 (at index 3), we see that 0 < 7. In a normal sorted array, we'd search left. Here, that would be a mistake, as 0 is in the right half.

The key insight is that even though the whole array isn't sorted, it's composed of parts that are.

This structure is what we will exploit. Our goal is to modify binary search to identify the sorted portion at each step and use that information to intelligently narrow down the search space.

2. Algorithm: Search in Rotated Sorted Array

The most elegant solution involves a single pass of binary search. At each step, with our left, mid, and right pointers, we have to answer two questions:

1. Which half is currently sorted (from left to mid, or from mid to right)?
2. Based on that, where could our target possibly be?

We can determine which half is sorted by comparing nums[mid] with the boundary element nums[left].

• If nums[left] <= nums[mid], the left half (left to mid) is sorted.
• Otherwise, the right half (mid to right) must be sorted.

Once we've identified the sorted half, we can check if the target falls within its range.

• If it does, we search within that half.
• If it doesn't, the target must be in the other, non-sorted half, so we search there.

This process is repeated, halving the search space at each iteration, preserving the $O(\log N)$ complexity.

The following video provides an excellent visualization and walkthrough of this exact logic. It breaks down the decision-making process for adjusting the left and right pointers in each scenario.

Now that you have the conceptual foundation, let's look at how this translates into code. The following resource provides a clear write-up and implementations. It covers both the more intuitive two-pass approach (first find the pivot, then search) and the optimized one-pass approach we just discussed.

3. A Different Twist: Almost-Sorted Arrays

Let's consider another variation you might encounter. What if the array is "almost sorted" or "nearly sorted"? In this context, it means an element that belongs at index i in a sorted array can be found at index i-1, i, or i+1.

For example: arr[] = [10, 3, 40, 20, 50, 80, 70]
Here, 3 is adjacent to 10, 20 is adjacent to 40, and so on.

Again, standard binary search fails. But since the displacement is strictly local (limited to adjacent positions), we can modify our search strategy.

The core idea is to check not just the middle element, but its neighbors as well.

1. Calculate mid.
2. Check if target is at arr[mid], arr[mid-1], or arr[mid+1].
3. If found, return the index.
4. If not, we need to decide which half to discard. If target < arr[mid], it must be in the left part. However, we can't just set right = mid - 1, because the element at mid-1 has already been checked. To ensure progress, we jump two steps: right = mid - 2. Similarly, if target > arr[mid], we set left = mid + 2.

This guarantees we shrink the search space at every step while accounting for the local displacements.

The following resource clearly explains this logic and provides a straightforward implementation.

Conclusion

In this lesson, we've elevated the classic binary search algorithm into a powerful, adaptable pattern. By learning to look for underlying structure in "broken" sorted arrays, we can preserve the coveted $O(\log N)$ time complexity that is critical for scalable solutions.

Key Takeaways:

• Modified Binary Search: The core pattern involves adapting binary search's search-space reduction logic to accommodate specific structural properties of an array (e.g., rotation, local displacement).
• Rotated Sorted Array: The key is to recognize that at least one half of the array is always sorted. By identifying the sorted half, you can determine whether to continue the search there or in the other half.
• Almost-Sorted Array: The key is to check the mid element and its immediate neighbors, then adjust the search pointers by two positions to ensure the search space is always reduced.
• Interview Mindset: These problems are designed to test your ability to reason about and adapt fundamental algorithms, a crucial skill for any senior engineer.

In our next lesson, we will move from searching problems to generative ones. You will learn how to use recursion and backtracking to solve problems that involve generating all possible subsets or combinations, a foundational technique for tackling a wide range of combinatorial challenges.