查找的三种常用算法

查找的定义：

给定一个值k，在含有n个元素的表中找出关键字等于k的元素。若找到，则查找成功，返回该元素的信息或该元素在表中的位置；否则查找失败，返回相关的指示信息。

我们最常见的查找莫过于对数组进行查找，比如：

但是接下来我们知道其实还有很多别的数据结构比如二叉树能够有效的进行查找。

若在查找的时候同时对表进行操作(如插入和删除)，则称为动态查找表，我们知道对数组进行动态查找效率是比较低的。

一些定义：

若在查找的时候不涉及对表进行操作(如插入和删除)，则称为静态查找表。

一个对查找效率的评价指标ASL(Average Search Length, 平均查找长度)：

线性表的查找 

 我们将介绍三种在线性表(可以将线性表理解为数组)上查找的方法：顺序查找、折半查找、分块查找。其中三种算法的效率：顺序查找O(n)<分块查找<折半查找O(logn)

顺序查找

不过多介绍，就是我们最熟悉的遍历，从头搜到尾。其ASL：

优点：简单，且对表的结构无特别要求，无论是用顺序表还是链表，也无论表是否有序，它都适用。缺点是效率低。

折半查找

又称为二分查找，其效率比较高。但是往往要求为有序表。

折半查找和顺序查找寻找元素37：

代码实现：

int BinSearch(int arr[], int arr_length, int k)
{
    int low = 0, high = arr_length - 1, mid;
    while(low <= high)
    {
        mid = (low + high) / 2;
        if(k == arr[mid])
            return mid + 1; //返回逻辑序号(arr[0]对应第一个元素)
        if(k < arr[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
    return(0); //未找到返回0
}

 

分块查找

在介绍分块查找前先介绍一下索引存储结构：

换句话说，索引存储结构相当于字典的目录索引功能，坐标的索引表就是目录，我们根据关键字在"目录"中查找对应的页码(地址)，得到了页码(地址)来寻找到对应的数据(主数据表中的区号、城市名、说明)。

在索引存储结构中进行关键字查找时先在索引表中快速查找(因为索引表中按关键字有序排列，可以采用折半查找)到相应关键字，然后通过对应地址找到主数据表中的元素。

索引存储结构可以提高按关键字查找元素的效率，其缺点是需要建立索引表而增加时间和空间的开销。

下面讲讲分块查找：

比如像下面这样将数据表分成5块，第一块最大元素为14，第二块最大元素为34，第三块为66，第四块为85，第五块为100。

 对于某个数k，我们先用折半查找(因为索引表是有序的)比较k和索引表中存储了每个块中的最大数据的表来确定k在哪块，比如我们要找78，66<78<85，因此在85这一块。然后再在块中用顺序查找等方式进一步查找得到k。代码就不放了。

ASL：

参考资料：

数据结构教程(第5版)