Modified Binary Search: Solving 'Search in Rotated Sorted Array'

Search in Rotated Sorted Array is a very good binary‑search problem because it forces us to let go of the simplest version of the technique without abandoning the core idea. The array is not fully sorted in the normal left‑to‑right sense, so the obvious reaction is often to give up on binary search and fall back to a linear scan.

That would work for correctness, but it misses the real lesson. We do not need the entire array to be perfectly ordered. We only need enough structure at each step to throw half of the search space away safely.

What Makes the Array "Rotated"

Take a sorted array like this:

[0, 1, 2, 4, 5, 6, 7]

If we rotate it, we might get:

[4, 5, 6, 7, 0, 1, 2]

The order is broken globally, but not everywhere. At any midpoint, one half is still sorted normally:

• either the left half is sorted
• or the right half is sorted

That is the key observation. Once we know which half is sorted, we can decide whether the target could live inside it. If not, we search the other half.

Why Binary Search Still Works

Binary search is really about safe elimination, not about worshipping perfectly sorted input.

At each step in this problem, we ask two questions:

1. Which side is definitely sorted?
2. Does the target fall within that sorted range?

If the left half is sorted and the target lies between values[left] and values[middle], then the answer must be on the left. Otherwise it must be on the right.

The mirror argument works when the right half is sorted.

That is enough to keep shrinking the search window in logarithmic time.

Walking through a Concrete Example

Take:

values = [4, 5, 6, 7, 0, 1, 2]target = 0

Start with:

• left = 0
• right = 6
• middle = 3

The midpoint value is 7.

Now compare the left boundary and the midpoint:

• values[left] = 4
• values[middle] = 7

That tells us the left half is sorted: [4, 5, 6, 7].

But the target 0 is not inside that sorted range, so we can discard the left half and continue on the right:

• left = middle + 1

Now the search space is [0, 1, 2], and the normal binary‑search logic finishes the job quickly.

This example is useful because it shows the real shape of the reasoning. We do not have to detect the pivot first. We only need to ask which half is sorted enough to trust right now.

A Practical TypeScript Solution

export const search = (values: number[], target: number): number => {  let left = 0;  let right = values.length - 1;  while (left <= right) {    const middle = Math.floor((left + right) / 2);    if (values[middle] === target) {      return middle;    }    if (values[left] <= values[middle]) {      const targetIsInLeftHalf =        target >= values[left] && target < values[middle];      if (targetIsInLeftHalf) {        right = middle - 1;      } else {        left = middle + 1;      }    } else {      const targetIsInRightHalf =        target > values[middle] && target <= values[right];      if (targetIsInRightHalf) {        left = middle + 1;      } else {        right = middle - 1;      }    }  }  return -1;};

Reading the Logic Without Getting Lost

The code becomes much easier to follow if we read it in this order:

• first, check whether the midpoint is the answer
• then identify the half that is definitely sorted
• then decide whether the target belongs inside that sorted half
• if yes, keep it
• if no, discard it and search the other side

That is all the algorithm is doing. The rotation changes the comparisons, but it does not change the underlying binary‑search discipline.

Why "One Half Must Be Sorted" is the Real Invariant

This is the part that usually makes the problem settle down mentally.

Because the array started sorted and was then rotated once, the breakpoint only exists in one place. That means both halves cannot be broken at the same time around the same midpoint. One side will still be in normal ascending order.

That is the trustworthy signal we use to decide where the target can still live.

If we internalise that rule, the algorithm stops feeling like a bag of special cases and starts feeling like a very ordinary binary search with a slightly richer comparison step.

Why Finding the Pivot First is Usually Unnecessary

Another common line of thought is:

• first find the rotation pivot
• then decide which sorted half should contain the target
• then run ordinary binary search inside that half

That is a valid strategy, and it can be a nice way to understand the problem the first time.

The reason I would not lead with it is that it introduces an extra phase we do not actually need. The modified binary search already discovers enough structure during the search itself:

• one sorted half
• one range check
• one elimination step

That keeps the whole solution in one loop instead of splitting the reasoning into pivot detection first and target search afterwards.

Common Mistakes

Assuming the Midpoint Tells Us Nothing Because the Array is Rotated

It still tells us quite a lot. The midpoint plus the left boundary or right boundary is enough to identify one sorted half.

Using the Wrong Range Checks

The comparisons must line up carefully:

• left sorted half: target >= values[left] && target < values[middle]
• right sorted half: target > values[middle] && target <= values[right]

Those inequalities are easy to blur together, and that is where many off‑by‑one bugs start.

Forgetting That Sorted‑Half Detection Depends on Distinct Values

In the classic problem, distinct values make the sorted‑half test decisive. If duplicates are introduced, some midpoint comparisons stop giving a clean answer.

Falling Back to Linear Search Too Quickly

Linear search is fine if the goal is only acceptance, but the point of this problem is to recognise that the structure still supports logarithmic elimination.

What About Duplicates?

The classic version of this problem assumes distinct values. That assumption matters because it keeps the sorted‑half test clean.

Once duplicates are allowed, the reasoning gets messier. We can end up in cases where the left, middle, and right values are the same, which makes it harder to identify a sorted half confidently. That becomes a different problem and usually needs extra handling.

For the standard version, though, the distinct‑values guarantee is exactly what makes this cleaner than it first appears.

Complexity and Why the Approach is Worth It

The time complexity is O(log n) and the extra space is O(1).

That is the obvious win, but the more useful gain is conceptual. This problem stretches the usual definition of binary search in a helpful way. It teaches us to look for local structure that still supports safe elimination even when the whole input is not globally neat.

Wrapping up

Search in Rotated Sorted Array is really a lesson in trusting the strongest local invariant available. We are not searching a perfectly sorted array, but at every step one half is still sorted enough to make a safe decision.

Key Takeaways

• Binary search depends on safe elimination, not on perfect global order.
• In a rotated sorted array, one half is always sorted at each step.
• The whole problem is deciding whether the target fits inside that sorted half.

Once that invariant becomes familiar, the rotated version feels much less exotic. It is still binary search. It is just paying closer attention.