## Wednesday, November 12, 2014

### [LeeCode] Find Minimum in Rotated Sorted Array I, II

Find Minimum in Rotated Sorted Array I

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.

Find Minimum in Rotated Sorted Array II

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.
The array may contain duplicates.

Search in Rotated Sorted Array I这题换汤不换药。同样可以根据A[mid]和A[end]来判断右半数组是否sorted：

(1) A[mid] < A[end]：A[mid : end] sorted => min不在A[mid+1 : end]中

(2) A[mid] > A[end]：A[start : mid] sorted且又因为该情况下A[end]<A[start] => min不在A[start : mid]中

(3) base case：
a. start =  end，必然A[start]为min，为搜寻结束条件。
b. start + 1 = end，此时A[mid] =  A[start]，而min = min(A[mid], A[end])。而这个条件可以合并到(1)和(2)中。

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14``` ```class Solution { public: int findMin(vector &num) { int start = 0, end = num.size()-1; while(start

3 1 2 3 3 3 3
3 3 3 3 1 2 3

A[mid] = A[end]：搜索A[start : end-1]

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16``` ```class Solution { public: int findMin(vector &num) { int start = 0, end = num.size()-1; while(startnum[end]) start = mid+1; else end--; } return num[start]; } }; ```