算法-旋转数组的最小数字

题目

输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为数组{1,2,3,4,5}的一个旋转,该数组的最小值为1。

旋转数组

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转,这本身没什么,但是如果旋转前的数组是一个排序好的递增数组,旋转数组就会有一些比较有意思的特性。

上图中是一个原数组与旋转数组,我们可以发现,旋转数组有两个排序好的子序列{3,4,5}和{1,2},我们要找的数值1(最小值)是两个子序列的分界值,也是第二个子序列的第一个值。

二分查找

二分查找算法是个很常见的查找算法,照比与顺序查找,它的速度更快,时间复杂度可以降低到O(log2n),具体的思想是:

首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。所以二分查找也叫作折半查找。

但是二分查找的使用有前提条件: 1.必须采用顺序存储结构; 2.必须按数值大小有序排列。

比如在{1,2,3,4,5}中查找4,首先数组满足二分查找的前提,那么先选定3,3<4,在右侧子表选定4,4=4,那么该数组中含有4。

二分查找应用在旋转数组的最小数字

讲道理的话,顺序数组发生了旋转已经就不满足二分查找算法的前提条件了,但是好在问题是旋转数组的最小数字,个人感觉这个理解很重要,本来二分查找满足前提条件的话适用于任意查找,而该任务只是在旋转数组中找最小,所以只有改一改二分的规则,还是可以用的。

首先让两个指针分别指向旋转数组的第一个位置(0)和最后一个位置(4),此时两个指针中间的数是5,5>3&&5>2,5比p1指向的数值(3)大,这说明中间的数值(5)在第一个子序列{3,4,5}中,那么第二个子序列一定在5的右面,最小的数字是第二个子序列的第一个数值,那么也一定在5的后面,此时为了缩小查找范围,构建子序列,就可以把p1调整到中间位置(2):

此时两个中间的数是1,1<5&&1<2,数值1比p2指向的数值(2)小,这说明中间数值(1)在第二个子序列中,那么最小数值一定在该数值的左面或者就是它,此时为了缩小查找范围,就可以移动p2到之间位置:

p1与p2位置只差1,那么此时p2指向的那个数就是最小数。

所以,传统的二分查找算法是两个指针在确定中间值,中间值与要查找的数值比较,以决定哪个指针移动到中间值以构建子表,最终查找结束的的条件是: 1.中间值与待查找数值相等 2.子表不存在

而在这个任务中的二分查找算法为,两个指针在确定中间值,中间值与两个指针指向的数值对比,以确定哪个指针移动到中间值以构建子表,最终查找结束的条件是: 两个指针指向的位置相差为1,p2指向的数值为最小数字。 关键之处在于指针移动的规则,这与传统的二分查找目的相同,都是为了在一次查找后缩小查找范围,所以规则就是,如果中间数字比p1指向的数字大(一般情况下一定比p2指向的大),那么移动p1,如果中间数字比p2指向的小(一般情况下一定比p1指向的小),那么移动p2。因为,p1永远在指向第一个子序列,p2永远再指向第二个子序列,而第二个子序列中最大的数都会比第一个子序列最小的数还要小,所以永远在和p1比大,和p2比小!!!

鲁棒性考虑

上面的方法适用于所有的旋转数组吗?显然不是: 1.如果旋转0或数组长度的整数倍时,数组依旧是递增的,此时该方法并不适用,解决方案为,初始状态下,如果p1指向的值小于p2,那么数组必然是顺序递增的:

2.如果旋转数组第一个位置的数字,最后一个位置的数字,中间数字三者相等,该方法并不适用,此时只能顺序查找:

代码实现

int Min(int* numbers, int length)
{
    if(numbers == NULL || length <= 0)
        throw new std::exception("Invalid parameters");

    int index1 = 0;
    int index2 = length - 1;
    int indexMid = index1;
    while(numbers[index1] >= numbers[index2])
    {
        //退出判断
        if(index2 - index1 == 1)
        {
            indexMid = index2;
            //退出while
            break;
        }


        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;
        //比小  移动p2
        else if(numbers[indexMid] <= numbers[index2])
            index2 = indexMid;
    }

    return numbers[indexMid];
}
//顺序查找
int MinInOrder(int* numbers, int index1, int index2)
{
    int result = numbers[index1];
    for(int i = index1 + 1; i <= index2; ++i)
    {
        if(result > numbers[i])
            result = numbers[i];
    }

    return result;
}

1.上面的代码来源于剑指offer,这套代码在操作数组时并没有用指针,可能是为了中间值的选取和退出条件更方便。 2.代码如何处理数组长度是偶数的情况?

indexMid = (index1 + index2) / 2;

直接取整,最后结果是一样的,大家随便举个例子试一下就好了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2598
来自专栏技术之路

wpf键盘记录器

很简单的一个wpf键盘记录器 ? 这个程序我一样用了全局勾子,之前用的都是winform上运行了,前一段时间 在国外的论坛上逛看到了一个wpf能用的就做了一个小...

2055
来自专栏marsggbo

Udacity并行计算课程 CS344 编程作业答案

892
来自专栏余生开发

echarts太阳分布图-饼图来回穿梭

var dom = document.getElementById("container");

1392
来自专栏Hadoop数据仓库

Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1866
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2702
来自专栏跟着阿笨一起玩NET

c# 使用timer定时器操作,上次定时到了以后,下次还未执行完怎么处理

------解决方案-------------------------------------------------------- 开始的时候,禁用定时器,你...

2981
来自专栏增长技术

App Guide相关

##TourGuide https://github.com/worker8/TourGuide

812
来自专栏码匠的流水账

java9系列(五)Stack-Walking API

java9新增这个类的目的是提供一个标准API用于访问当前线程栈,之前只有Throwable::getStackTrace、Thread::getStackTr...

471
来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1182

扫码关注云+社区