How do you search for a value in a rotated sorted array?
Short answer: A sorted array rotated at an unknown point (e.g. {4, 5, 6, 7, 0, 1, 2}) can still be searched in O(log n). At each binary-search step, at least one half is properly sorted. Check whether the target lies inside that sorted half's range; if so, search it, otherwise search the other half.
#include <stddef.h>
long search_rotated(const int *a, size_t n, int target) /* distinct values */
{
size_t lo = 0, hi = n; /* [lo, hi) */
while (lo < hi) {
size_t mid = lo + (hi - lo) / 2;
if (a[mid] == target) return (long)mid;
if (a[lo] <= a[mid]) { /* left half [lo, mid] is sorted */
if (a[lo] <= target && target < a[mid]) hi = mid;
else lo = mid + 1;
} else { /* right half [mid, hi-1] is sorted */
if (a[mid] < target && target <= a[hi - 1]) lo = mid + 1;
else hi = mid;
}
}
return -1;
}
/* {4, 5, 6, 7, 0, 1, 2}, target 0 -> 4 */
Dry run (target 0): lo 0, hi 7, mid 3 (7). Left half 4..7 sorted, 0 not in [4, 7) → lo 4. mid 5 (1). a[4]=0 <= a[5]=1: left half sorted, 0 in [0, 1) → hi 5. mid 4 (0) → found at 4.
Duplicates (e.g. {1, 1, 1, 3, 1}) break the "which half is sorted" test when a[lo] == a[mid] == a[hi-1]; then you can only shrink by one (lo++), and the worst case becomes O(n).
Related: find the rotation point (the minimum) with binary search comparing a[mid] with a[hi-1].
Embedded relevance: a circular log or ring buffer of timestamped records written in order and wrapped around is exactly a rotated sorted array; this search finds a record by timestamp without unrolling the buffer.