## 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]; } }; ```

1. it's a very elegant solution!

2. 你好，有个更一般的问题。在做binary sesarch的时候，循环条件怎么设定？start < end 还是start <= end,
还有怎么缩放边界，end = mid 还是end = mid -1 .这个我一直无法把握，请问有什么技巧？谢谢

1. 固定模板：while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return nums[mid];
} else if (nums[mid] < target) {
start = mid;
} else {
end = mid;
}
}
基本可以应付90%的二分法