【算法】先生,您点的查找套餐到了(二分、插值和斐波那契查找)

参考资料

《算法(java)》                           — — Robert Sedgewick, Kevin Wayne

《数据结构》                                  — — 严蔚敏

Interpolation Search[插值查找]     — —  维基百科

Fibonacci Search[斐波那契查找]   — —  GeeksforGeeks 

根据输入的一个关键字(Key),  在一个有序数组内查找与该关键字值相等的元素, 若找到则将该元素的下标返回, 若未查找到则返回 -1。 这是一种很常见的操作。

今天的文章主要介绍在有序数组中的三种查找方法:

  • 二分查找
  • 插值查找
  • 裴波纳契查找

数据量很小的情况下, 我们可能会选择用顺序查找的方式处理。

顺序查找

顺序查找, 就是逐个遍历数组中的每一个元素,逐个比较它们和关键字是否相等,当查找到相等元素时, 遍历停止。

例如在下面这个数组中查找值为8的元素的下标,  查找成功需要进行9次比较。

当数组的规模逐渐扩大时候, 因为比较次数太多,顺序查找耗时太长。 所以我们想, 有什么方法能减少比较的次数呢?

二分查找

在介绍二分查找前, 先让我来插一段故事。。。

这个名扬京华的食府, 在一天的多数时辰里,都是坐无虚席。

就在这时,一位慕名前来的食客。在等候许久后,终于等来了他点的菜品。

这位客人,叫做有序数组。

“先生您好, 这是您点的查找套餐”, 店小二终于赶了过来。 摆上了第一道菜。

“二分菜系么”,客人轻语着, 瞧见那盛菜的雪色素瓷上, 清晰的镌刻着 1/2 这个数字。

客人笑了,“仅凭一道家常菜,便能艳压京华众食府, 贵店的厨子果然名不虚传呢”

(未完待续)

咳咳,回到正文——二分查找

二分查找的思想

设置一个循环,不断将数组的中间值(mid)和被查找的值比较如果被查找的值等于a[mid],就返回mid; 否则,就将查找范围缩小一半。如果被查找的值小于a[mid], 就继续在左半边查找;如果被查找的值大于a[mid],  就继续在右半边查找。 直到查找到该值或者查找范围为空时, 查找结束。

基于数组的有序性, 每次都将当前的数组分为两半, 通过关键字和中间元素的比较, 立即排除掉其中不可能存在和键值相等的元素的那一半

这样,每次减少的一半元素的比较, 前后叠加起来, 就是二分查找相对于顺序查找提高的性能。

二分查找代码

/**
 * @Author: HuWan Peng
 * @Date Created in 22:55 2017/12/7
 */
public class BinarySearch {
  /**
   * @description: 二分查找
   * @param a:   待查找数组
   * @param key: 查找的关键字
   */
  public static int search (int [] a, int key) {
    int low = 0;
    int high = a.length-1;
    int mid;
    while(low<=high){
      mid = (low + high)/2;
      if(key<a[mid]) {
        high = mid - 1;
      }
      else if(key>a[mid]) {
        low = mid + 1;
      }
      else {
        return mid;
      }
    }
    return -1;
  }
}

点击这里在线运行代码!

通过mid = (low + high) / 2,并比较Key和a[mid]大小, 根据比较的结果, 用high = mid - 1和low = mid + 1 “丢掉”一半的元素(从mid = (low + high) / 2 可以看出被排除的一半元素不会纳入到下一次的比较中了)

整个过程中,左游标 low 和右游标 high 互相靠近, 最后的结果可能有两个:

1. 在low和high交叉前(low>high) 查找成功,查找结束 

2.  数组中没有和关键字等值的元素, 最后low和high交叉(low>high), 跳出while循环, 返回 -1。

二分查找轨迹

下图所示的是我们在数组中查找关键字为8的元素的过程, 一开始的时候左右游标分别指向数组的首末位置

根据左右游标的下标取中间位置下标 mid = (0 + 9)/2 = 4,  而a[mid] = a[4] = 4,  Key = 8, 因为Key>a[mid],所以Key必定出现在mid的右半边, 左半边的元素可排除(a[0]~a[4]), 将左半边待比较的元素“丢弃”。 丢弃”的方法是将左游标 low 移动到当前 mid 右边相邻的位置 这样左半边的元素就不会出现在下次比较中了。

根据左右游标的下标取中间位置下标 mid = (5 + 9)/2 = 7,  而a[mid] = a[7] = 7,  Key = 8, 因为Key>a[mid],所以Key还是在数组的右半边,  mid左半边的元素可排除(a[5]~a[7]), 丢弃左半边待比较的元素——将左游标low移动到 8 的位置。

根据左右游标的下标取中间位置下标 mid = (8 + 9)/ 2 = 8, 而a[mid] = a[8] = 8, Key = 8, 因为Key == a[mid], 查找成功。

使用了二分查找后,  我们仅仅只比较了3次(比起比较了8次的顺序查找)

插值查找

看到这里你可能有点累了,再来段故事(接上文)

客人并没有像其他食客那样,面对珍馐美味而饕餮一番。

而是浅尝一口后, 用手巾擦擦嘴, 对店小二道:

“《二分》这道菜味道固然不错,软滑香糯,鲜美多汁”

“可这并不是你们大厨最富盛名的菜色吧!”,客人朗声说道, 平静的脸上似有似无地飘着几分愠怒的神色。

店小二一惊, 深知这位客人不是好伺候的主。“请您稍等!”,小二说完后便禀报大厨。

一刻钟后, 第二道菜上来了。

“插值菜系么?” 这位口味刁钻的客人竟面露喜色,又重新拿起了调羹。

(未完待续)

回到正题:

插值查找的思路

上面的二分查找,每次是从数组的中间位置查找的, 让我们把思维发散一下: 查找的位置一定要从中间开始查找吗?

打个比方: 我们在一本英文字典里面查找apple这个单词的时候, 你肯定不会从字典中间开始查找, 而是从字典开头部分开始翻,因为觉得这样的找法才是比较快的。

这给我提供了一个思路: 如果能在查找前较准确地预测关键字在数组中的位置的话,这样设计出的查找方法能比二分查找提高更多的性能! 基于这种思想,我们设计了插值查找的算法。

插值查找和二分查找非常相似, 只要对原代码做少许变动就可以了。

二分查找中关键的一行代码,是mid = (low + high) / 2, 转变一下就是mid = low + (high - low)/2,   (high-low)后面乘的这1/2就是二分查找每次查找的位置。要实现插值查找, 只要把这里的1/2替换成我们所预测的关键字的位置占数组总长度的比例就可以了。

这个比例,可以用公式(key - a[low])/ (a[high] - a[low])来计算, 合起来插值查找对mid的计算公式是:

mid = low + (high - low)*(key - a[low])/ (a[high] - a[low])

元素数值均匀分布的有序数组里面, 用这种方法查找是很快的。特别的,对绝对均匀分布的数组(相邻元素差值相同), 插值查找用一次比较就能查找成功

当然了, 前提是数组中元素数值是均匀分布的, 如果是对 1,2,40,99,1000这种分布很不均匀的数组, 插值查找的计算会起到反效果, 就不如二分查找了

插值查找代码

代码如下:

/**
 * @Author: HuWan Peng
 * @Date Created in 23:09 2017/12/7
 */
public class InterpolationSearch {
  /**
   * @description: 插值查找
   */
  public static int search (int [] a, int key) {
    int low = 0;
    int high = a.length-1;
    int mid;
    while(a[low]!=a[high]&&key>=a[low]&&key<=a[high]){ // 这个判断条件很重要! 不能缺少
      mid = low + (high - low)*(key - a[low])/(a[high] - a[low]);
      if(key<a[mid]) {
        high = mid - 1;
      }
      else if(key>a[mid]) {
        low = mid + 1;
      }
      else {
        return mid;
      }
    }
    if(key == a[low]) return low; // 如果是 2,2,2,2,2这种全部重复元素,返回第一个2
    else return -1;
  }
}

点击这里在线运行代码!

注意, 一定要保证两点:

  1. a[low]!=a[high] ( 插值公式里分母是a[high] - a[low],不能等于0)
  2. a[low]<=key<=a[high]

用这两点作为while循环的判断条件。

while循环里的判断条件可以是low<=high吗?

不可以!! 这有可能导致在查找不存在的值时,让代码陷入while死循环

因为插值查找和二分查找很相似, 很多同学可能会想: 那我只要把mid = (low + high) / 2换成插值公式不就可以了嘛? 其他不变就OK啦。

但请注意:

mid = low + (high - low)*(key - a[low])/(a[high] - a[low]);

这个公式里, (key - a[low])在计算过程中是可能出现负值的,这个时候mid的变化就不是mid = low + 一个正值。 而是mid = low + 一个负值,  mid会出现意外减少的情况,如果这个时候又刚好key>a[mid]的话, 那么low也会减少,因为:

      else if(key>a[mid]) {
        low = mid + 1;
      }

然后原本只能增加(向右移动)的左游标low竟然减少(向左移动)了!

下面用debug测试: 在 1,4,6,9,11,66,78中查找22时, 每一轮的low和hign游标的值

用[low,high]表示,变化如下:

[0,6]
[1,6]
[2,6]
[3,6]
[4,6]
[5,6]
[3,6]  // low从5倒退到3的位置, 开始死循环
[4,6]
[5,6]
[3,6] // 第二轮的死循环.....
......

原因也就是我上面所说的, 因为插值公式的计算里, key - a[low]计算出了负值, 在这个例子中是22 - 66 = -44所导致的。

如果你去百度“插值查找”, 几乎所有博客都告诉你,  while循环里的判断条件是while(low<=high)。

对此,我只想说:

更多的可以看看这里:

插值查找——维基百科

处理边缘情况:重复元素

A.

有一种很讨厌的边缘情况,那就是输入的数组全部都是重复元素,例如2,2,2,2因为while循环里的a[low]!=a[high]的判断条件,所以它并不会进入while循环并造成可怕的“除0”错误 但如果这个时候刚好key = 2, 我们总不能返回 -1 吧,所以在while循环下面我们设置了这一段代码:

    if(key == a[low]) return low; // 如果是 2,2,2,2,2这种全部重复元素,返回第一个2
    else return -1;

B .

你可能还担心一种情况,那就是: 对1,2,2,2,3,5这样的数组, 一开始的时候是能进入while循环的,但万一在循环中发生了a[low] - a[high] = 0 导致“除0”错误怎么办呢?  放心,从逻辑上可以判断这不会发生, 因为low和high并不会同时使a[low]和a[high]等于2, 这一点我们分类讨论:

  1. 对上面的数组,假设重复元素就是Key,那么当a[low]或a[high]取到该元素时就跳出while循环了
  2. 假设重复元素不是Key, 例如是3, 这时high不动,low会一直右移直到跳过2
  3. 假设重复元素不是Key,且Key不存在,例如查4,分析同2

裴波那契查找

能看到这里真是辛苦你了, 继续一段上面的故事

《插值菜系》上桌后, 已经被客人吃完了一半。这时,他却把调羹放下了。小二觉察,漫步前来。

“非常美味的料理,称之为山珍海味也不为过” , “然而, 却仍然不是我最想吃到的那道菜。”

小二愣了, 就算是权倾朝野的显贵登临, 也未曾说过此番言语。

“你们的主厨, 可是姓裴?” 

店小二顿时醒悟, “请您再稍等片刻!”, 说完后便前去告知厨子

片刻, 上了第三道菜。 已经很多年没人点这道菜了, 以至于它早在这家食府的菜单上遗失。

这道菜看上去很少, 碗里却好似托着着山与海

那盛菜的青花玉盘的釉面上,清晰地镌刻着“1、1、2、3、5、8、13、21”等一连串数字。

(未完待续)

进入正题

裴波那契查找的来源

裴波那契数列是一串按照F(0)=1,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)这一条件递增的一串数字:

1、1、2、3、5、8、13、21 ... ...

两个相邻项的比值会逐渐逼近0.618 —— 黄金分割比值。这个非常神奇的数列在物理,化学等各大领域上有相当的作用, 于是大家想: 能不能把它用在查找算法上嘞??

于是就有了裴波那契查找算法, 裴波那契数列最重要的一个性质是每个数都等于前两个数之和(从第三个数字开始)。 也就是一个长度为f(n)的数组,它能被分成f(n-1)和f(n-2)这两半, 而f(n-1)又能被分为f(n-2)和f(n-3)这两半。。。直到分到1和1为止(f(1)和f(2))。

(注意一个细节: 在分割时,可以选择将“大块”的f(n-1)放前面部分,也可以将“小块”的f(n-2)放前面,我下面的分割都是按照“大块”在前进行的)

这里我们发现,二分查找, 插值查找和裴波那契查找的基础其实都是:对数组进行分割, 只是各自的标准不同: 二分是从数组的一半分, 插值是按预测的位置分, 而裴波那契是按它数列的数值分。

三个数组以及它们之间的关系。

了解裴波那契查找的算法实现, 最重要的是理解“三个数组”之间的关系,它们分别是:

  • 待查找数组 (a)
  • 裴波那契数组(fiboArray)
  • 填充后数组(filledArray)

裴波那契数组

要按裴波那契数分割, 我们当然要创建一个容纳有裴波那契数的数组,那么,怎么确定这个数组的长度呢? 或者说, 怎么确定数组里裴波那契数的最大值呢?(最后一个值)

答:只要刚好能满足我们的需要就可以了,裴波那契数组的长度,取的是大于等于待查找数组长度的最小值。原数组长4则取5,长6则取8,长13取13(1、1、2、3、5、8、13、21 )

填充数组

其次我们要考虑的是: 我们的数组长度不可能总是满足裴波那契数的, 例如5、8、13、21等是裴波那契数, 但我们的数组长度可能是6,7,10这些非裴波那契数, 那这时候怎么办呢?  总不能对长度为10的待查找数组按照8和13进行第一次分割吧, 所以我们应该按照上面选定的裴波那契数组的最大值, 创建一个等于该长度的填充数组, 将待查找数组的元素依次拷贝到填充数组中, 剩下的部分用原待查找数组的最大值填满。

我们进行查找操作的并不是原待排序数组, 而是对应的填充数组!

查找到填充的部分元素如何处理?

当我们在填充数组中查找成功后,该元素可能来源于在原数组的基础上填充的部分元素(上图黄色9), 返回的下标(10,11,12)显然是不准确的,而应该返回原数组的最后一个元素的下标(9) 。

所以,解决方法就是: 在填充数组中查找成功后, 判断返回的元素下标和原数组长度的关系,如果:返回下标 > 原数组长度 - 1, 那么改为返回原数组最后一个元素下标就OK了。

查找过程

OK,有了上面的基础我们总结下查找的过程:

  1. 根据待查找数组长度确定裴波那契数组的长度(或最大元素值)
  2. 根据1中长度创建该长度的裴波那契数组,再通过F(0)=1,F(1)=1, F(n)=F(n-1)+F(n-2)生成裴波那契数列为数组赋值
  3. 以2中的裴波那契数组的最大值为长度创建填充数组,将原待排序数组元素拷贝到填充数组中来, 如果有剩余的未赋值元素, 用原待排序数组的最后一个元素值填充
  4. 针对填充数组进行关键字查找, 查找成功后记得判断该元素是否来源于后来填充的那部分元素

具体代码

/**
 * @Author: HuWan Peng
 * @Date Created in 16:54 2017/12/7
 */
public class FibonacciSearch {
  /**
   * @description: 创建最大值刚好>=待查找数组长度的裴波纳契数组
   * @param a: 待查找的数组
   */
  private static int[] makeFiboArray(int[] a){
    int N = a.length;
    int first = 1,sec = 1,third=2,fbLength = 2;
    int high = a[N-1];
    while (third<N) { // 使得裴波那契数不断递增,直到值刚好大于等于原数组长度为止
      third = first + sec; // 根据f(n) = f(n-1)+ f(n-2)计算
      first = sec;
      sec = third;
      fbLength++; // 计算最后得到的裴波那契数组的长度
    }
 
    int [] fb = new int[fbLength]; // 根据上面计算的长度创建一个空数组
    fb[0] = 1; // 第一和一二个数是迭代计算裴波那契数的基础
    fb[1] = 1;
    for(int i=2;i<fbLength;i++){
      fb[i] = fb[i-1] + fb[i-2]; // 将计算出的裴波那契数依次放入上面的空数组中
    }
 
    return fb;
  }
  /**
   * @description: 裴波那契查找
   */
  public static int search (int [] a, int key) {
    int low, high;
    int lastA;
    int [] fiboArray = makeFiboArray(a); // 创建最大值刚好>=待查找数组长度的裴波纳契数组
    int filledLength = fiboArray[fiboArray.length-1];
    int [] filledArray = new int[filledLength]; // 创建长度等于裴波那契数组最大值的填充数组
 
    for(int i=0;i<a.length;i++) {
      filledArray[i] = a[i]; // 将原待排序数组的元素都放入填充数组中
    }
 
    lastA = a[a.length-1]; // 原待排序数组的最后一个值
    for (int i=a.length;i<filledLength;i++) {
      filledArray[i] = lastA; // 如果填充数组还有空的元素,用原数组最后一个元素值填满
    }
 
    low = 0;
    high = a.length; // 取得原待排序数组的长度 (注意是原数组!)
    int mid;
    int k = fiboArray.length -1;
    while(low<=high) {
      mid = low + fiboArray[k-1]-1;
      if(key<filledArray[mid]) {
        high = mid-1; // 排除右半边的元素
        k= k-1;       // f(k-1)是左半边的长度
      }else if(key>filledArray[mid]) {
        low = mid+1;  // 排除左半边的元素
        k = k-2;      // f(k-2)是右半边的长度
      }else {
        if(mid>high){ // 说明取到了填充数组末尾的重复元素了
          return high;
        }else {
          return mid; // 说明没有取到填充数组末尾的重复元素
        }
      }
    }
    return -1;
  }
}

点击这里在线运行代码

斐波那契查找的轨迹

我百度“斐波那契查找”的时候, 一大部分基于数组实现的代码都是创建了一个长度固定为20的斐波那契数组。

而第20个斐波那契数是6765,所以这样的代码只能处理长度小于等于6765的数组。

于是就有了另一种编写斐波那契数组的方法: 不依赖数组的编码方法,请看:

不依赖数组的斐波那契查找

请点这里:

不依赖数组的斐波那契查找(C语言)

说一下这种方法和我上面介绍的方法的不同点

  • 我上面介绍的版本: 先把斐波那契数算出来,再全部用数组存起来, 要用的时候直接从数组里拿就可以了
  • 这个版本: 不用数组存, 只算出来需要的最大的斐波那契数, 要用的时候“临时”计算就可以了

二分,插值和裴波纳契查找的性能比较

二分查找:

二分查找的轨迹可以用一颗判定树来表示,例如:将下面的[20,30,40,50,80,90,100]表示为一颗判定树, 因为一开始查找的是位于整个数组1/2 位置的元素50, 所以将50置于根元素位置, 接下来查找的是30或90,所以放到50的子节点的位置。

结合一个结论:具有n个节点的判定树的深度为logn2 + 1, 所以二分查找时候比较次数最多为logn2 + 1,

插值查找

上面也说过了,插值查找只适用于关键字均匀分布的表,在这种情况下, 它的平均性能比二分查找好,在关键字不是均匀分布时, 它的性能表现就不足人意了。

斐波那契查找

斐波那契查找的平均性能比二分查找好, 但最坏情况下的性能(虽然仍然是O(logn))却比二分查找差,它还有一个优点就是分割时候只需进行加减运算(二分和插值都有乘/除)

故事结尾

“能品尝到裴先生的手艺,我等食客之幸也”,

说完这句话, 食客便从店小二的视野里消失了

。。。。。。。。。。。。

——“等等! 你TM还没付饭钱就想走!!”

——“哎呀卧槽! 忘带钱了!”

于是这位食客像豪猪一般在京城的街道上奔跑, 在日暮的夕阳之下映出两人的背影, 此乃后话

(全文完)

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

3098: Hash Killer II

3098: Hash Killer II Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge S...

2736
来自专栏机器之心

资源 | 从算法到数据结构,百道面试问题实现答案集合

选自GitHub 作者:Sherali Obidov 机器之心编译 参与:李亚洲、微胖、蒋思源 该资源是算法、数据结构以及面试问题解决方案的集合,里面的 rep...

2496
来自专栏ml

HDU----(4549)M斐波那契数列(小费马引理+快速矩阵幂)

M斐波那契数列 Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (J...

3135
来自专栏数据魔术师

基础算法| 常用排序算法小结

日常吹水 说到这个算法, 可能瞬间大家就觉得那些灰机昏膏素什么的比这个生动活泼多了。 那么,正走在算法之路上的你, 是否还在苦苦寻求修仙之路? 是否被各种排序...

2965
来自专栏向治洪

图算法之bfs、dfs、prim、Dijkstra

概述 在图算法中经常要执行遍历每个顶点和每条边的操作,即图搜索。许多图算法都以图搜索为基础,如2-着色问题、连通性计算基于深度优先搜寻(depth-first ...

2576
来自专栏Leetcode名企之路

【Leetcode】59. 螺旋矩阵 II

给定一个正整数 n,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

750
来自专栏窗户

Scheme来实现八皇后问题(1)

  皇后是国际象棋里杀力最强的子,它可以吃掉同一条横线、竖线上其他棋子,也可以吃掉所在的两条斜线上的其他棋子(当然在角上只有一条斜线)。

1194
来自专栏决胜机器学习

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(六)——数组的相乘、广义表 (原创内容,转载请注明来源,谢谢) 本文接PHP数据结构(五)的内容。 4.2 行逻辑链接的顺序表 行逻辑链接的顺...

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

二叉树的遍历

解决二叉树的很多问题的方案都是基于对二叉树的遍历。遍历二叉树的前序,中序,后序三大方法算是计算机科班学生必写代码了。其递归遍历是人人都能信手拈来,可是在手生时写...

3344
来自专栏算法修养

卡特兰数总结

中间部分,小部分内容摘自百度百科 结尾部分,小部分内容摘自http://blog.sina.com.cn/u/1885661061 卡特兰数是组合数学中一个...

2896

扫码关注云+社区