You know how to binary search a sorted array. But what if the array is not sorted?

Here is an array: [4, 5, 6, 7, 0, 1, 2]. It was sorted, then someone rotated it — the tail wrapped around to the front. The target is 0.

You cannot compare arr[mid] with the target the usual way — the global ordering is broken. arr[3] = 7 is greater than arr[4] = 0, which violates the sorted assumption. A standard if (arr[mid] < target) lo = mid + 1 would look at arr[3] = 7 > 0 and conclude “target is in the left half” — wrong, because the left half is [4, 5, 6, 7] and 0 is in the right half.

Linear scan works, but it is O(n). The question is whether you can still discard half the array at each step without a global sort order to rely on. Think about what the rotation preserves. The array [1, 2, 3, 4, 5, 6, 7] rotated by 4 becomes [4, 5, 6, 7, 0, 1, 2]. The global sort is broken, but look at the two pieces: [4, 5, 6, 7] and [0, 1, 2]. Each piece is still sorted internally. The rotation broke one adjacency but preserved all others.

What property of this array does survive the rotation?

Find the target in a rotated array. Then try a mountain array. At each step, predict what happens before you see it.

The rotated array has a powerful property: even though the global sort is broken, one of the two halves is always fully sorted. In [4, 5, 6, 7, 0, 1, 2] with mid = 3:

• Left half [4, 5, 6, 7] is sorted (because arr[lo] <= arr[mid])
• Right half [0, 1, 2] contains the rotation point

Once you know which half is sorted, you can check whether the target falls in that sorted range. If it does, search there. If it does not, search the other half. Either way, you discard half the array.

function searchRotated(arr: number[], target: number): number {

  let lo = 0, hi = arr.length - 1;

  while (lo <= hi) {

    const mid = lo + Math.floor((hi - lo) / 2);

    if (arr[mid] === target) return mid;

    if (arr[lo] <= arr[mid]) {

      // Left half is sorted

      if (arr[lo] <= target && target < arr[mid]) {

        hi = mid - 1;  // target is in sorted left half

      } else {

        lo = mid + 1;  // target must be in right half

      }

    } else {

      // Right half is sorted

      if (arr[mid] < target && target <= arr[hi]) {

        lo = mid + 1;  // target is in sorted right half

      } else {

        hi = mid - 1;  // target must be in left half

      }

    }

  }

  return -1;

}

For mountains, the comparison changes entirely. There is no target value — you are looking for the peak. The gradient tells you which direction to climb: if arr[mid] < arr[mid + 1], the peak is to the right. If arr[mid] > arr[mid + 1], the peak is to the left or at mid.

You just searched three structures that look nothing alike: a rotated array, a mountain, and (if you count sorted) a flat ramp.

In every case, the strategy was the same: one comparison discards half the space.

For sorted arrays, that comparison is arr[mid] vs target. For rotated arrays, it is “which half is sorted, and is the target there?” For mountains, it is “which direction is uphill?”

The details change. The principle does not. Binary search does not require sorting. It requires discardability — the guarantee that a single check eliminates half the candidates. A structure is binary-searchable if and only if you can write a predicate on mid that reliably tells you which half to keep.

Think about what all three structures share. In a sorted array, arr[mid] < target eliminates the left half. In a rotated array, “the sorted half does not contain the target” eliminates that half. In a mountain, “the slope is increasing” eliminates the left half. Each is a different predicate, but each produces the same binary outcome: left or right.

The insight generalizes further. Binary search does not require sorting. It requires a single property: one comparison at the midpoint tells you which half to discard. The comparison can be anything — a value comparison, a structural check, a gradient test, a feasibility predicate. As long as the answer to “which half?” is deterministic, binary search works.

Here is a quick reference for the structural variants you are most likely to encounter:

// LC 33: Search in Rotated Sorted Array

// Predicate: which half is sorted? Is target in that range?

// Template: exact-match (lo <= hi, return mid on match)

// LC 153: Find Minimum in Rotated Sorted Array

// Predicate: arr[mid] > arr[hi] means min is in right half

// Template: boundary (lo < hi, hi = mid)

// LC 162: Find Peak Element

// Predicate: arr[mid] < arr[mid+1] means peak is rightward

// Template: boundary (lo < hi, hi = mid)

// LC 74: Search a 2D Matrix

// Predicate: flatten to 1D with row=mid/cols, col=mid%cols

// Template: exact-match on virtual 1D array

Rotated array search (LC 33) is not a special algorithm to memorize. It is standard binary search with a richer predicate. Peak finding (LC 162) is binary search on the gradient. 2D matrix search (LC 74) is 1D binary search with index arithmetic. The moment you see “discard half with one check,” you have binary search — whatever the container looks like.