vlambda博客
学习文章列表

想必大家在学习编程语言时，一定都已经遇到过了有关二分查找的问题。或许你会认为二分查找是一类很简单的问题，但事实真的是如此吗？

我们先来看看二分查找的基础版本，也是大家最熟悉的版本。给定一个有序不重复数组，再给一个目标数字，要求程序返回目标数字的下标。

这个问题用简单的二分查找就能实现。我们每次都取中间下标的数字与目标数字比较大小，然后一步步折半缩小查找范围。程序如下：

时间复杂度度分析：最坏情况下需要O（logN）的复杂度

现在我们有这样一个有序可重复数组 arr=[1,1,2,2,2,3,3,3,3,5,5,7,8,8,9,9,9],要求返回这个数组中大于等于3数字中排在最左边的数的下标。具体到这个数组中，我们需要返回的下标是5。

在这个问题中，我们依然可以用二分查找实现，不过不同的是，我们需要在每次的判断条件中，都要加上对于中间下标与左邻数字的比较，当中间下标左邻数字已经不满足我们题给的条件时，我们就可以跳出程序了。程序如下：

时间复杂度：无论怎么样查找，都必须进行O（logN）的时间复杂度。

以上两个案例的共同点是用来二分查找的数组都是有序的，那么无序数组能不能进行二分查找呢？

当然是可以的！

现在我们有这样一个问题，我们定义一个局部最小值的概念，假设数组的下标最大值为N。当下标为0的数（最左边的数），比下标1的数（右邻数）小，我们可以说这是一个局部最小值；相同的，倒数第一个数只要比倒数第二个数小，我们也说这是一个局部最小值；对于中间的数，只要它比左邻和右邻的数小，我们就说它是一个局部最小值。现在给定的一个无序数组，满足任意相邻数字不相同，要求我们返回任意一个局部最小值的下标。

首先，我们可以先假设一般情况，局部最小值不在首和尾，这个时候在首尾位置必定满足如图的数字趋势。

那么，我们就知道，在中间必定存在某个数是局部最小值，作为转折点，接下来我们取中间下标m，可能会出现下面的情况

那么在0到m位置必定会出现局部最小值，怎么样，相信大家已经领悟这道题背后的二分思想了吧，接下来让我们用代码实现：

时间复杂度在最坏情况下为O（logN）。

二分查找作为一种基础算法，背后蕴含的原理不仅适用于有序数组，也可以是无序数组，学习算法过程中，我们不能只局限于某个问题的理解，要学而有思，举一反三。

• 参考文献：

1、一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶

https://www.bilibili.com/video/BV13g41157hK?spm_id_from=333.1007.top_right_bar_window_default_collection.content.click

今天的小知识就到这儿啦

下周一锁定SUIBE数据科学系

我们继续与你分享专业小知识！

 内容制作|葛飞翔

    图文排版|张康晨

内容审核|葛飞翔