一、题干
牛客网链接
https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba
二、题解
作为查找类问题，往往通用的办法是暴力搜索。和前面的练习一样，本文不对暴力搜索算法进行过多的说明，而主要介绍二分查找算法在寻找轮转数组轮转点时的运用。暴力搜索的时间复杂度为O(N)，而二分查找算法的时间复杂度为O(logN)，是一种更优的解法。
二分查找：分治与不断区间划分锁定元素
一个长度为 n 的非降序数组，把一个数组最开始的若干个元素“平移”到数组的末尾，就变成了一个旋转数组。如数组 [ 1,2,3,4,5 ]，经过轮转变成 [ 4,5,1,2,3 ]，后两个元素成了最前面的两个元素。对于轮转数组特性更多的介绍，可以戳 👇 轮转数组问题：如何实现数组“整体逆序，内部有序”？“三步转换法”妙转数组
最基础的二分法适用于在一个已经有序数组的中寻找某一元素。本题相当于该题的变式。本题中的轮转数组被分成了有序的两个部分，如 [ 4,5,1,2,3 ] 中，虽然数组整体是无序的，但其中 [ 4,5 ] 和 [ 1,2,3 ] 仍然是有序的两个部分，在这种部分有序情况下，也可以使用二分查找法来解答，总体思路与二分法查找峰值的算法思路有些类似。
思路
1. 声明 left、right 双指针，分别指向 array 数组的最左端（首元素）与最右端（最后一个元素）。轮转数组内的最小值相当于一个“谷底”，它的左右两边的数都比它本身要大，且左侧的数一定比右侧的数还要大。我们要做的就是把这个“谷底”元素找出来。
2. 以 mid = (left + right) / 2 来表示中间值。通过比较中间值 arr[mid] 与 a[right] 的大小来不断划分搜索区间，从而锁定元素：
若 arr[mid] > arr[right] ，则说明最小元素一定在 mid 的右边部分。左界右移：left = mid + 1
若 arr[mid] < arr[right]，则说明最小元素可能就在 mid 位置，或在 mid 位置的左侧。右界左移： right = mid。
若 arr[mid] == arr[right]，这时就无法直接判断出最小元素的位置区间了。我们选择将右界right挨个左移，逐步缩减右界以便寻找。
代码
int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) { int left = 0; int right = rotateArrayLen - 1; int flag = 0; int mid = 0; while(left < right){ mid = (left + right) >> 1; if(rotateArray[mid] > rotateArray[right]){ left = mid + 1; }else if(rotateArray[mid] == rotateArray[right]){ right--; }else{ right = mid; } } return rotateArray[left]; //或return rotateArray[mid];此时while处需写while(left <= right) }
三、总结
1. （部分）有序数组的查找问题，首先考虑使用二分法解决。其可将遍历法时间复杂度的线性级别降低至对数级别。
2. 二分查找的本质的本质是二段性，只要满足二段性的问题都可以使用二分查找求解。在本题中二分查找的二段性体现在：最小值左边的单调增，最小值右边的单调增。且左边的元素都大于右边的元素。
图源：牛客网题解
图源：牛客网题解
3. 解决分段单调问题，只需比对arr[mid]，arr[0]和arr[numsSize - 1]的大小关系即可：
arr[mid] > arr[0]，则最小值在 mid 位置的右半部分。
arr[mid] < arr[numsSize - 1]，则最小值在 mid 位置的左半部分。
4. 必要时可以通过画图来判断边界位置的情况。
“花式”二分查找相关题型：
1.二分查找法巧得峰值
2.杨氏矩阵查找
“轮转数组”知识点：
1.轮转数组问题：如何实现数组“整体逆序，内部有序”？“三步转换法”妙转数组
