Given a sorted array of distinct integers that has been rotated at some unknown pivot, return the index of target if present, else -1. Must run in O(log n).
1 ≤ nums.length ≤ 5000-10⁴ ≤ nums[i], target ≤ 10⁴nums are unique.nums is sorted in ascending order, then possibly rotated (it may not be rotated at all).At each step, decide whether the left or right half is sorted.
A rotated sorted array is two climbing runs placed side by side. In [40,50,60,10,20,30] they are 40,50,60 and 10,20,30, and the only place the values go down is the drop between them.
Time O(log n)Space O(1)
The full walkthrough and code are part of Premium
4