Search in Rotated Sorted Array
Problem: Array was sorted, then rotated at some pivot. Find target.
Key: At least one half is always sorted!
• If arr[left] ≤ arr[mid] → Left half is sorted
• Otherwise → Right half is sorted
• Check if target is in sorted half, search there; else search other half
Time: O(log n)