欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【二分查找】旋转数组的最小数字

程序员文章站 2024-03-08 20:00:34
...

查找和排序

查找和排序都是经常用的,相对来说查找比较容易,一般就是顺序查找二分查找哈希表查找二叉排序树查找。哈希表主要的优点是能在O(1)时间内查找某一元素,缺点是实现哈希表需要额外的空间。

排序比查找复杂,一般要掌握插入排序冒泡排序归并排序快速排序选择排序等,并能比较算法优劣。

面试题11:旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。

这题是在二分查找基础上做了一些修改的,旋转后的两个子数组是各自有序的,而最小数字(旋转前的第一个数字)正是在两个子数组交界的位置:
【二分查找】旋转数组的最小数字
和二分查找一样,设置两个指针(游标)分别指向第一个和最后一个元素,每次取中间元素。如果落在前一个子数组区间,就看后一半;如果落在后一个子数组区间,就看前一半。

这里”落在哪个子数组区间”可以通过和两个游标对应的元素值进行比较来判断。但是也存在特例,因为没有规定数组旋转前是严格递增的,旋转后可能形成这样的数组:
【二分查找】旋转数组的最小数字
这种时候只能顺序查找来寻找最小元素。

另外,”旋转”可以是将前面0个数字拿到后面,所以只要判断第一个数字小于最后一个数字时,第一个数字就是最小的,直接返回。

#include<bits/stdc++.h>
using namespace std;

// 参数:
//        numbers:     要查找的数组首地址
//        index1:      查找的起始游标
//        index2:      查找的结束游标
// 返回值:
//        找到的最小数字
int MinInOrder(int* numbers, int index1, int index2) {
    int result = numbers[index1];//从起始游标处开始
    //遍历整个游标范围
    for(int i = index1 + 1; i <= index2; ++i) {
        //如果发现比当前result更小的数
        if(result > numbers[i])
            result = numbers[i];//记录之
    }
    return result;//最终找到的就是最小的 
}


// 参数:
//        numbers:     旋转后的数组首地址
//        length:      数组的长度
// 返回值:
//        找到的最小数字
int Min(int* numbers, int length) {
    //输入合法性校验
    if(numbers == nullptr || length <= 0)
        throw new exception();

    int index1 = 0;//初始化游标P1
    int index2 = length - 1;//初始化游标P2
    int indexMid = index1;//indexMid最终将指向数组中最小的数,初始化为一个数
    //这样在这个循环前判断,如果发现数组中第一个数小于最后一个数,就可以直接返回第一个数
    while(numbers[index1] >= numbers[index2]) {
        //[找到最小数的条件]
        //如果index1和index2指向相邻的两个数
        //则index1指向第一个递增子数组的最后一个数字
        //index2指向第二个子数组的第一个数字,也就是数组中的最小数字
        if(index2 - index1 == 1) {
            indexMid = index2;//记录下index2为所求
            break;
        }

        //如果下标为index1、index2和indexMid指向的三个数字相等
        //则只能顺序查找,因为无法判断该走向哪一边
        //但能确定一定还在[index1,inedx2]这个游标区间内
        indexMid = (index1 + index2) / 2;
        if(numbers[index1] == numbers[index2] && numbers[indexMid] == numbers[index1])
            return MinInOrder(numbers, index1, index2);//返回顺序查找的结果

        //缩小查找范围
        //如果中间数不小于P1数,说明分界点在后面
        if(numbers[indexMid] >= numbers[index1])
            index1 = indexMid;//所以将P1后移
        //如果中间数不小于P2数,说明分界点在前面面
        else if(numbers[indexMid] <= numbers[index2])
            index2 = indexMid;//所以将P2前移
    }
    return numbers[indexMid];//最终,中间数点就是分界点,即为所求
}

int main(){
    int array[] = { 3, 4, 5, 1, 2 };
    try{
        cout<<Min(array,5)<<endl;
    }catch(...){
        cerr<<"Invalid parameters"<<endl;
    }
    return 0;
}