Leetcode: Find Minimum in Rotated Sorted Array

Difficulty: Medium

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.

Subscribe to see which companies asked this question

Hide Tags

 Array Binary Search

Show Similar Problems

-------------------------------------

-------------------------------------

Decide how to turn left or right, see figure below:

There are four cases. Identify the four cases is the key to solve the problem. 

Note: Any case 2 and case 3, after binary search, will be reduced to the case 1 and case 4. While case 1 and case 4 could be easily found the minimal value. 

/////////////////////////////////////

//codes

class Solution {

 public:

        int findMin(vector<int>& nums) {

               //check input

               int len = nums.size();

               //if(len==1)return nums[0];

               int l = 0, r = len - 1, mid = l + (r - l) / 2;

               while (l<r){

                      if (nums[l]<nums[r])return nums[l];

                      else if (nums[mid] >= nums[l]) l = mid + 1;//"=" used as there are conditions like mid==L

                      else r = mid;

                      mid = l + (r - l) / 2;

               }

               return nums[r];

        }

 };