什么是二分查找、插值查找、斐波那契查找和索引查找？

Love The Way You Lie 2022-11-19 14:59 167阅读 0赞

## 引言 ##

原文链接：[顺序表和有序表的查找算法][Link 1] [线性索引查找][Link 2] 希望点进去的小伙伴关注一下我的公众号哟，文末有二维码，谢谢！

## 1、查找是什么？ ##

<table> 
 <tbody> 
  <tr> 
   <th>术语</th> 
   <th style="width:665px;">解释</th> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">查找表</td> 
   <td style="vertical-align:top;width:665px;">同一类型数据元素构成的集合</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">关键字</td> 
   <td style="vertical-align:top;width:665px;">数据元素中某个数据项的值</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">查找</td> 
   <td style="vertical-align:top;width:665px;">根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">静态查找表</td> 
   <td style="vertical-align:top;width:665px;">查找时不做插入或删除操作。适用于用线性表存储，可以采用顺序查找或折半查找</td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;">动态查找表</td> 
   <td style="vertical-align:top;width:665px;">查找时会有插入或删除操作，适用于二叉树。</td> 
  </tr> 
 </tbody> 
</table>

先介绍两种查找算法：

*  顺序表查找：这个就是按顺序从前往后查找，没啥好说的。
 *  有序表查找（必须有序）

有序表查找有三种：

*  折半查找（二分查找）
 *  插值查找
 *  斐波那契查找（待补充）

## 2、折半查找 ##

优点：

相对于顺序查找而言，效率高。

缺点：

1.  如果经常插入或删除元素，则还需要另外维护元素的有序性，而且由于是顺序存储，会带来不小的工作量。
2.  如果要查的是一个很小的元素，为什么要从中间开始折半查找呢？
    
    比如\[1,3,5,9,10,20,35,39,50,78,139\]这个顺序表，我想查3这个元素，从中间的位置开始折半查找效率并不是很高。
3.  这时候就出来一个插值查找，是对二分法的改进。

## 3、插值查找 ##

折半查找的公式是：

middle\_index = (min\_index+max\_index)/2

将上面的公式做一下数学变换：

middle\_index =min\_index+1/2\*(max\_index-min\_index)

这个公式的意思是：

middle\_index =最小索引+(最大索引与最小索引差值的二分之一)

重点就在于这个二分之一，插值查找的改进方案是：

将1/2换成(key-a\[min\_index\])/(a\[max\_index\]-a\[min\_index\])

a是数组名，key是要查找的值。

## 3、斐波那契查找 ##

斐波那契数列(又叫兔子数列、黄金分割数列)

如果兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一

对小兔子来。假设所有兔都不死，那么一年以后可以繁殖多少对兔子？

![图片][7e7763e6678e7474f877022544d380b8.png]

这个数列有一个很明显的特征，每一项的值等于前两项之和。用数学函数来定义，如下图所示。

![图片][a3c66a606d4084cdb8c8377dc86cb472.png]

那和黄金分割又有什么关系呢？

因为随着数列项数的增加，前一项与后一项之比越来越逼近黄金分割的数值 0.6180339887

## 4、线性索引查找 ##

上面讲到了顺序表和有序表的查找：

*  顺序表的查找效率是最低的
 *  有序表的查找相对而言比较快，但这是建立在有序的基础上，如果数据量非常大，维护有序性代价太大了，一般大量的数据都是按先后顺序入库的

对于这样的查找表，解决办法就是通过索引。索引是为了加快查找速度而设计的一种数据结构。

索引有多个索引项，而每个索引项至少包含关键字和对应的记录在存储器中的位置两个字段。

索引按存储结构可分为如下几种：

*  线性索引：也叫索引表，用线性结构存储索引项
 *  树形索引
 *  多级索引

线性索引又可以分为如下三种：

*  稠密索引
 *  分块索引
 *  倒排索引

下面简单介绍一下这三种索引。

### 4.1、稠密索引 ###

数据集中的每一个记录都对应一个索引项，即数据与索引是一对一关系。

假如有一万条数据，那么就对应一万条索引项，数据是无序的，而索引项是有序的，通过有序表的查找算法先查找索引项，然后再通过一对一关系迅速找到数据。

这种索引的缺点很明显，就是太占空间了。

### 4.2、分块索引 ###

分块索引的典型例子是图书馆的书架。

分块就是将数据集分成若干块，块内可以无序，而块间是有序的。

每个索引项有三个字段：

*  对应分块的最大关键字
 *  块长
 *  块首数据元素的指针

分块与索引项的关系如下图所示。

![图片][9f1002236dcd200079ae0fca46bd977f.png]

查找步骤就是：

*  如果要查找关键字62，因为57<62<96，根据块首指针，很容易定位到第三块的块首
 *  由于块内无序，因此只能在第三块内顺序查找

### 4.3、倒排索引 ###

搜索引擎中最基础的搜索技术就是倒排索引。

假如有两篇文章，然后我们把每篇文章的关键字提取出来，如下表所示。

我们可以根据某篇文章找到该文章的关键字，这样的存储结构叫正排索引。

相反地，如果能根据关键字找到对应的文章，就叫倒排索引，因此我们可以将存储结构做一下变换，如下表所示。

## 我的二维码 ##

觉得写得不错的小伙伴，扫码关注一下我的公众号吧，谢谢呀！

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70][]

[Link 1]: https://mp.weixin.qq.com/s?__biz=MzI1NTc1MDU3Mw==&mid=2247484494&idx=1&sn=41ccab9b008559c8f1495c88f99b7763&chksm=ea307c8cdd47f59af2a0af0e884068e270e1f0d4d0d107865d119b5c852ff06c6f9d93c19ca8&token=505395671&lang=zh_CN#rd
[Link 2]: https://mp.weixin.qq.com/s?__biz=MzI1NTc1MDU3Mw==&mid=2247484509&idx=1&sn=9a850a3794926cf3f60972599cecec06&chksm=ea307c9fdd47f589f2ab2ca7fbb8e76b39c04257103e9e18c2e11413d5a331fbc012801463e0&token=505395671&lang=zh_CN#rd
[7e7763e6678e7474f877022544d380b8.png]: /images/20221119/d105c903935848a98f12bdf1b4fd0257.png
[a3c66a606d4084cdb8c8377dc86cb472.png]: /images/20221119/278f9565793541e796107db7c7f08a25.png
[9f1002236dcd200079ae0fca46bd977f.png]: /images/20221119/a1e7381dfba049c2b54d148b9a08b1b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hsXzE4MDM_size_16_color_FFFFFF_t_70]: /images/20221119/c30429e9bfe344e5a2a769db7d381cdc.png