153. Find Minimum in Rotated Sorted Array

Modified binary search. Instead of checking nums[mid] == target, we check if nums[lo] < nums[hi]. If so, the minimum is nums[lo]. Otherwise, we just need to keep looking for the rotated pivot. There are two cases:

Case 1: nums[mid] < nums[lo]
[7,6,1,2,3,4,5], the pivot must be on the left of mid. Since pivot is on the left, the mid itself could be the minimum too, so the high boundary will be mid.

Case 2: nums[mid] >= nums[lo]
[4,5,6,7,0,1,2], the pivot must be on the right of mid. So the low boundary will be mid+1.

1:  class Solution {  
2:  public:  
3:    int findMin(vector<int>& nums) {  
4:      int lo = 0, hi = nums.size()-1;  
5:      while (lo < hi) {  
6:        if (nums[lo] < nums[hi]) {  
7:          return nums[lo];  
8:        }  
9:        int mid = lo + (hi - lo) / 2;  
10:        // [4,5,6,7,0,1,2]  
11:        if (nums[mid] >= nums[lo]) {  
12:          lo = mid + 1;  
13:        } else {  
14:          // [7,6,1,2,3,4,5]  
15:          hi = mid;  
16:        }  
17:      }  
18:      return nums[lo];  
19:    }  
20:  };