Binary Search Searching a sorted array
234. Search in Rotated Sorted Array
You are given an array of distinct integers nums and an integer target. The array was sorted in increasing
order and then rotated. Return the index of target in nums, or -1 if target is not in nums.
Rotating an array by k takes its first k elements off the front and puts them, in the same order, at the
back. For example, [2,4,6,8,10] rotated by 2 is [6,8,10,2,4]. The rotation can be any amount from 0 to
nums.length − 1, and you are not told which. A rotation by 0 leaves the array sorted.
Indexes start at 0. Aim for a running time of O(log n).
Example 1
Input: nums = [15, 18, 22, 3, 7, 9, 11], target = 9
5Explanation: The array is [3,7,9,11,15,18,22] rotated by 4. In nums itself, 9 sits at index 5.
Example 2
Input: nums = [40, 50, 10, 20, 30], target = 35
-1Explanation: 35 would fall between 30 and 40, but no element of nums equals it, so the answer is −1.
Example 3
Input: nums = [-8, -3, 0, 6], target = -8
0Explanation: This array was rotated by 0, so it is still sorted. The target is the first and smallest element, at index 0.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-109 ≤ nums[i] ≤ 109-109 ≤ target ≤ 109- All values of
numsare distinct. numsis an increasing array rotated by some amount from 0 tonums.length − 1.
Clarifying questions
What you would ask an interviewer before writing any code.