LeetCode 33 Search in Rotated Sorted Array - Example and Complexity Analysis

Trace nums = [4, 5, 6, 7, 0, 1, 2] with target = 0.

left = 0, right = 6. mid = 3, nums[mid] = 7.

Is left half sorted? nums[0] = 4 <= nums[3] = 7. Yes.

Is target in [4, 7]? No (0 < 4). Search right: left = 4.

left = 4, right = 6. mid = 5, nums[mid] = 1.

Is left half sorted? nums[4] = 0 <= nums[5] = 1. Yes.

Is target in [0, 1]? Yes (0 >= 0 and 0 <= 1). Search left: right = 4.

left = 4, right = 4. mid = 4, nums[mid] = 0. Found! Return 4.

Each iteration halves the search space. $O(\log n)$ time, $O(1)$ space.