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

题目

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

相关文章

来自专栏竹清助手

【机器学习】 搭建模型第一步:你需要预习的NumPy基础都在这了

NumPy 主要的运算对象为同质的多维数组,即由同一类型元素(一般是数字)组成的表格,且所有元素通过正整数元组进行索引。在 NumPy 中,维度 (dimens...

1174
来自专栏Java Web

最大子段和问题

问题描述: 给定长度为n的整数序列,a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大,或者求出最大的这个和。如果该序列的...

3495
来自专栏数据结构与算法

22:神奇的幻方

22:神奇的幻方 总时间限制: 1000ms 内存限制: 65535kB描述 幻方是一个很神奇的N*N矩阵,它的每行、每列与对角线,加起来的数字和都是相同的。...

3357
来自专栏ACM算法日常

递归算法复杂度Ω分析-分享

1. 深入认识递归 (1) 递归执行过程 例子:求N!。 这是一个简单的"累乘"问题,用递归算法也能解决。 n! ...

371
来自专栏Java 源码分析

Java位操作

     无论说是在哪一门计算机语言,位操作运算对于计算机来说肯定是最高效的,因为计算机的底层是按就是二进制,而位操作就是为了节省开销,加快程序的执行速度,以及...

2798
来自专栏Java帮帮-微信公众号-技术文章全总结

09.Java图形打印

09.Java图形打印 Java 实例 – 打印菱形 输出指定行数的菱形。 实例 ? 输出结果: ? ---- Java 实例 – 九九乘法表 输出九九乘法表。...

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

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

  对象的初始化 在声明类时直接对数据成员初始化是错误的!下面的例子时错误的!! class Time{ hour =0; minitu=0; sec=0; }...

2836
来自专栏mathor

ST算法

 RMQ(Range Minimum/Maximum Query),即区间最值查询。对于长度为n的数列arr,回答若干询问Q(i,j),返回数列arr中下标在i...

892
来自专栏北京马哥教育

史上最简单!冒泡、选择排序的Python实现及算法优化详解

1、排序概念 内部排序和外部排序 根据排序过程中,待排序的数据是否全部被放在内存中,分为两大类: 内部排序:指的是待排序的数据存放在计算机内存中进行的排序过程;...

4524
来自专栏Python小屋

Python运算符含义汇总

本文以Python 3.5及其以后的版本为主进行介绍。 运算符功能说明+算术加法,列表、元组、字符串合并与连接-算术减法,集合差集*乘法,序列重复/真除法//求...

2817

扫码关注云+社区