DAY-7 | 牛客-BM21 寻找旋转数组的最小元素：二分法分治思想真的很可靠

C语言好题方法总结。日积月累，慢慢进步！

目录

一、题干

二、题解

二分查找：分治与不断区间划分锁定元素

思路

 代码

三、总结

---

一、题干

牛客网链接

BM21 旋转数组的最小数字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.轮转数组问题：如何实现数组“整体逆序，内部有序”？“三步转换法”妙转数组

---