Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.
Example 1:
Input: [3,4,5,1,2] Output: 1
Example 2:
Input: [4,5,6,7,0,1,2] Output: 0
Description taken from https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/.
#O(log(N)) Time, O(1) Spaceclass Solution: def findMin(self, nums: List[int]) -> int: left, right = 0, len(nums) - 1 while left < right: middle = (left + right) // 2 if nums[middle] < nums[right]: right = middle else: left = middle + 1 return nums[left]We can solve this question using a binary search.
A clue that this algorithm can be utilized is if we are given a problem where either the input or the output is sorted, and we are looking for a specific target within that input or output.
Where we need to adjust a general binary search algorithm is where we decide to move the left and right pointers in each iteration. Typically, we would move these if the mean value is higher or lower than the target.
Here, we will need to move these in order to find the non-rotated portion of the array.
We will start by initializing our left and right pointers to be the first and last elements of the array.
left, right = 0, len(nums) - 1
We are looking for the element that should be at the left-most position of the sorted array.
While our pointers haven't overlapped, we’ll set the middle pointer as the mean of the left and right positions.
while left < right: middle = (left + right) // 2
We will check if the middle element is less than the right. If the array isn't rotated then we would expect the minimum to be the left-most position. If the middle element is less than the right then that means we're in a nonrotated portion of the array so we will move leftward as expected.
if nums[middle] < nums[right]: right = middle
Otherwise, we are in a rotated portion of the array so we will move the left pointer rightward, so that we can move to the nonrotated portion of the array that is on the right side, and we will continue searching for the minimum.
else: left = middle + 1
Once we have broken from our loop, we can return the element at our left or right pointer since they overlapped on this number, it will be the minimum.
return nums[left]