旋转数组的最小数字（二分）
2021-02-15 10:17
标签：线性查找 最小数 ext 相等 cto array span 情况 out 题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的一个旋转，该数组的最小值为1。 分析： 1， 2， 3， 4， 5 的一个旋转是 3， 4， 5， 1， 2，通过二分，5 与 3 、 5 与 2 比较，可以得出右边的子数组必定无序，故最小值一定在右边。 1， 2， 3， 4， 5 的另一个旋转是 5， 1， 2， 3， 4，用过二分，2 与 5 、 2 与 4比较，可以得出左边的子数组必定无序，故最小值一定在左边。 多尝试几个例子发现，最大值和最小值一定总在一起（本质因为数组的旋转），而这个导致了左右子数组的无序。 注：1， 1， 1， 0， 1 是特殊的例子，它的中间值与左右边界都相等，此时无法判断，但可以截取这段数组暴力地线性查找。 从上面的代码可以看出有三条分支，分别是左子数组无序、右子数组无序、无法判断而线性查找三种情况。 注意循环的出口，此题中只剩下两个数时就能判断，此时需要直接跳出，否则程序会无限循环。 旋转数组的最小数字（二分） 标签：线性查找 最小数 ext 相等 cto array span 情况 out 原文地址：https://www.cnblogs.com/Black-treex/p/12715971.html/*
* 旋转数组的最小数字
*/
int baoli(vectorint> arr, int a, int b)
{
int ans = INF;
for (int i = a; i )
{
if (ans > arr[i])
ans = arr[i];
}
return ans;
}
int minNumberInRotateArray(vectorint> rotateArray)
{
int left = 0, mid = 0;
int right = rotateArray.size() - 1;
while (left + 1 right) {
// 若边界不等，则二分(说明无序)
mid = (left + right) >> 1;
if (rotateArray[mid] rotateArray[left]) {
right = mid;
}
else if (rotateArray[mid] > rotateArray[right]) {
left = mid;
} // 若边界相等，暴力查找
else {
return baoli(rotateArray, left, right);
}
}
return rotateArray[right];
}
int main()
{
vectorint> rotateArray = {1, 1, 1, 0, 1};
cout endl;
return 0;
}