[Algorithm] Find Minimum in Rotated Sorted Array

[Algorithm]Find Minimum in Rotated Sorted Array

Problem statement

Suppose a sorted array 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.

Solution 

There is only one pivot point in this array. So for each subarray [lhs, rhs], consider following situation -

1. nums[lhs] < nums[rhs] - the pivot point must be outside of this subarray, the minimum value should be nums[lhs].

2. If nums[lhs] > nums[rhs] - the pivot point must be inside this array. Then take the middle element ( mid = lhs + (rhs-lhs)/2 ). The minimum should be the pivot point number.

• nums[mid] >= nums[lhs] - pivot point must be in the second half, then we shift the scope to be [mid+1, rhs]
• Num[mid] < nums[lhs] - pivot point must be in the first half, then we shift the scope to be [lhs, mid] 

Code Implementation

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: int findMin(vector<int>& nums) { int lhs = 0; int rhs = nums.size()-1; while (lhs < rhs) { if (lhs == rhs-1) return std::min(nums[lhs], nums[rhs]); int mid = (lhs + rhs) / 2; if (nums[mid] < nums[rhs]) { rhs = mid; } else { lhs = mid+1; } } return nums[lhs]; } };