Hints — p33 Search in Rotated Sorted Array

Read one at a time.

Hint 1 — O(log N) means binary search. Even though the array is rotated, you must do O(log N). Linear scan is wrong even though it would pass time limits.

Hint 2 — The key invariant. A rotated sorted array has exactly ONE drop. So for any mid, ONE of the two halves [lo..mid] and [mid+1..hi] is fully sorted (the drop is in the other half).

Hint 3 — Which half is sorted? One comparison. Compare nums[mid] to nums[lo]:

• If nums[lo] <= nums[mid], the LEFT half is sorted.
• Else, the RIGHT half is sorted.

(Note the <= — when lo == mid, the left half is the trivial single-element sorted array.)

Hint 4 — Narrow into the sorted half if target is there.

• Left sorted: target ∈ left iff nums[lo] <= target < nums[mid]. If yes, hi = mid - 1; else lo = mid + 1.
• Right sorted: target ∈ right iff nums[mid] < target <= nums[hi]. If yes, lo = mid + 1; else hi = mid - 1.

Hint 5 — Loop frame.

lo, hi = 0, len(nums) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    if nums[mid] == target: return mid
    ...
return -1

Inclusive lo, hi; while lo <= hi; always move past mid on narrowing (mid - 1 or mid + 1). Never lo = mid (infinite loop).

If still stuck: see solution.py. 12 lines for the main loop.