剑指Offer——旋转数组的最小数字

时间:2023-03-08 17:54:28

题目描述:

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

分析:

二分查找的变形。慢慢缩小查找的区间,直到找到为止。

代码:

 class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
int Len = rotateArray.size();
if(Len == ) return ;
int left = , right = Len - , mid;
while(left <= right) {
mid = (left + right) >> ;
int leftNum = rotateArray[left];
int rightNum = rotateArray[right];
int midNum = rotateArray[mid];
if(leftNum < rightNum) return leftNum;
if(midNum > rightNum)
left = mid + ;
else if(midNum < rightNum)
right = mid;
else {
left++;
right--;
}
}
return rotateArray[mid];
}
};