这道题主要采用二分查找的思想，如果 mid 左边包含被切开的数字，那么它的右边的大小顺序一定是正常的（rotateArray[right]>rotateArray[mid]），而左边是不正常的rotateArray[left]>=rotateArray[mid]，反之亦然，所以根据这个来判断下一次循环的边界的划分，不过需要注意的是，这里不是查找数字大小，所以不能让边界为right=mid-1或left=mid+1，最开始我在这里出现了思维惯性，所以判断失误，卡了很久。另外需要注意的地方就是这里的序列是非减序列，所以如果出现相等数字的话，就需要使用使用遍历进行判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if(rotateArray.size()==0) return 0;
int left=0,right=rotateArray.size()-1,mid;
while(left<right){
mid=(left+right)/2;
int i=mid-1,j=mid+1;
while(i>=left && rotateArray[mid]==rotateArray[i]) i--;
while(j<=right && rotateArray[mid]==rotateArray[j]) j++;
if(rotateArray[i]>=rotateArray[mid] && rotateArray[j]>=rotateArray[mid])
return rotateArray[mid];
else if(rotateArray[right]>=rotateArray[mid]) right=mid;
else if(rotateArray[left]<=rotateArray[mid]) left=mid;
}
return mid;
}
};
|