LeetMotion
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed).
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
1 <= nums.length <= 5000-10⁴ <= nums[i] <= 10⁴nums are unique.nums is an ascending array that is possibly rotated.-10⁴ <= target <= 10⁴The simplest way to search for an element in any array is to iterate through it.
0 to n-1.nums[i] == target, return i.Thoughts: This is an $O(n)$ solution. We must do it in $O(log\ n)$ time using Binary Search, meaning we have to smartly figure out which way to halve the array despite the rotation!
In a rotated sorted array, one half of the array will ALWAYS be perfectly sorted! We can use this strictly sorted half to determine if our target falls logically within its boundaries.
nums[L] <= nums[M], we know the Left half is sorted continuously. So, if target > nums[M] OR target < nums[L], it physically cannot be in the left half. We must go right: L = M + 1. Otherwise, go left R = M - 1.nums[L] > nums[M], we know the Right half is sorted continuously. So, if target < nums[M] OR target > nums[R], it physically cannot be in the right half. We must go left: R = M - 1. Otherwise, go right L = M + 1.
Discussion
…