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

题目

输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{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 条评论
登录 后参与评论

相关文章

来自专栏King_3的技术专栏

leetcode-561-Array Partition I

1757
来自专栏五毛程序员

Cocos2d-x基础篇C++

2493
来自专栏测试开发架构之路

C++之类和对象的使用(三)

对象数组 如果构造函数只有一个参数,在定义数组时可以直接在等号后面的花括号内提供。Student stud[3]={90,92,01};//合法 如果构造函数...

3219
来自专栏猿人谷

旋转数组的最小数字

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

1918
来自专栏柠檬先生

jquery操作DOM 元素(3)

.detach()   从DOM 中去掉所匹配的元素。     .detach([selector])       select...

1748
来自专栏海天一树

小朋友学Java(9):抽象类与接口

之前提过面向对象有三大特性:封装、继承、多态。 还有另一种说法,即面象对象有四大特性:抽象、封装、继承、多态。 这两种说法都是对的,不必拘泥于哪种说法。关键要能...

2699
来自专栏angularejs学习篇

angularjs学习第八天笔记(指令作用域研究)

angularjs其作用域通过scope来实现,其取值有三种情况:true、false、{}

691
来自专栏前端架构

JavaScript-数据结构和算法(程序=数据结构+算法)

数据结构是对在计算机内存中(有时在磁盘中)的数据的一种安排。包括数组、链表、栈、二叉树、哈希表等。

421
来自专栏书山有路勤为径

递归函数基础

函数代码中调用自己时称为递归,该函数被称为递归函数。递归函数是一个很高效的 开发技巧,可以极大的简化代码提高开发效率。递归函数与循环类似,循环可以完成的 事情,...

703
来自专栏程序员互动联盟

【编程基础】Java里面如何对字符串排序?

前几天有同学在群里问一个Java面试题,上面的思路很正确大概分为几步: 1、分割字符串: 用到的方法是String类的 public String[] spl...

3489

扫码关注云+社区