## What is it? Search for a target value in a sorted array that has been rotated at some unknown pivot point. Binary search still works because at least one half of the array is always sorted. ## How it works - Compute `mid = (low + high) / 2` - Determine which half is sorted: - If `arr[low] <= arr[mid]` → left half is sorted - If `target` is in `[arr[low], arr[mid])` → search left; else search right - Else → right half is sorted - If `target` is in `(arr[mid], arr[high]]` → search right; else search left - Repeat until found or `low > high` ## When to use - Searching in a rotated sorted array (LeetCode 33) - Any problem where the array has a single inflection point ## Key Points - O(log n) — binary search still applies because one half is always sorted - Handle duplicates separately — they can reduce worst case to O(n) - The key insight: at least one of the two halves is always sorted