Binary search on a rotated array

O(log n)

Run binary search on an array that was sorted then rotated: at every step at least one half is still properly sorted, so check which one and decide from there.

Signals

sorted array rotated at an unknown pivotfind a target in O(log n)no duplicates (or handle them separately)find the minimum / the rotation pointarray increases then drops once

Template

function searchRotated(arr, target) {
    let lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        if (arr[mid] === target) return mid;
        if (arr[lo] <= arr[mid]) {
            if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

Looks similar, isn't

Binary search (array): Plain binary search assumes arr[lo] <= arr[mid] <= arr[hi] everywhere. A rotated array is not fully sorted, so the ordinary compare-to-mid rule breaks; you must first identify which half is sorted, then check if the target lies in that half.

sorted-then-rotated array, n up to 1e5+, need better than O(n) -> O(log n) time, O(1) space. Rotated + still asking for log n is the cue that you need the sorted-half check, not plain binary search.

Learn this pattern