Search in Rotated Sorted Array

Concepts: pyRotatedArray, pyBinarySearchVariants

This is the most common binary search interview question at FAANG companies. LeetCode 33. The array [4, 5, 6, 7, 0, 1, 2] was once sorted, then rotated at some pivot. You need to find a target in O(log n). The candidates who fail this question all have the same problem: they memorized the code pattern without understanding the invariant. When they see a variation, they are lost. Do not memorize the code. Understand the invariant, and the code writes itself. The Core Invariant In any rotated sorted array, when you split at mid, at least one of the two halves is guaranteed to be sorted (non-rotated). You can determine which half is sorted by comparing nums[left] with nums[mid]. If nums[left] <= nums[mid], the left half is sorted. Otherwise the right half is sorted. Once you know which half i