LeetMotion
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.[0,1,2,4,5,6,7] if it was rotated 7 times.Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums are unique.nums is sorted and rotated between 1 and n times.The simplest way to find the minimum element in any array is to iterate through it and keep track of the smallest seen value so far.
min_val = infinity.x in the array.min_val = min(min_val, x). Return min_val.Thoughts: This entirely defeats the purpose of the array being originally sorted. We must use binary search to get the $O(log\ n)$ constraint.
In a rotated sorted array, one half of the array will ALWAYS be perfectly sorted, while the other half will contain the rotation "pivot" (which is the true minimum).
res and the newly found nums[M].nums[L] < nums[R], the current search space is already perfectly sorted. The minimum of this subspace is definitively nums[L]. Update res and break immediately.nums[M] >= nums[L], then the left half is sorted (and purely ascending, meaning it holds larger values), so the absolute minimum must be on the right side. Shrink left: l = m + 1.nums[M] < nums[L], the right half is continuous, and the pivot point is backwards in the left half! Shrink right: r = m - 1.
Discussion
…