查找

2018-10-10 本文已影响0人 ahuustcly

1. 概述

查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的
数据元素。

查找表按照操作方式分为：静态查找表和动态查找表。

静态查找表：只作查找操作的查找表
动态查找表：在查找的过程中，会同时的插入查找表中不存在的数据元素，或者删除已经存在的某个元素

2. 顺序查找

最基本的查找技术，适合于存储结构为顺序存储或者链式存储的线性表，时间复杂度为O（n）

int sequence_search(int a[],int n, int key)
{
    for (int i = 0; i < n; i++)
    {
        if (key == a[i]){
            return i;
        }
    }
    return -1;
}

3. 有序查找

二分查找
又称为折半查找，前提条件是线性表中的记录必须是有顺序的，即采用顺序存储，时间复杂度为O（logn）。基本思想为：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；反之，则在中间记录的右半区继续查找，不断重复上述步骤直至查找成功。

int binary_search(int a[], int n, int key)
{
    int low = 0;
    int high = n - 1;
    int mid;
    while (low < high)
    {
        mid = (low + high) / 2;
        if (key == a[mid])
        {
            return mid;
        }
        else if (key < a[mid])
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }
    return -1;
}

插值查找
原先的，mid = low + ½（high - low），
改进为，mid = low + (key - a[low]) / (a[high] - a[low]) (high - low)
基本思想为：插值查找是根据要查找的关键字key与查找表中的最大最小记录的关键字比较后的查找方法。从时间复杂度来看为O（logn），但是其平均性能要比折半查找好很多。
斐波那契查找
利用斐波那契数列的黄金分割原理来实现。
改进为，mid = low + F[k-1] - 1,其中k为斐波那契数列的下标，F[k-1]为斐波那契数列。

4. 线性索引查找

索引就是把一个关键字与它对应的记录相关联的过程。这里主要关注三种线性索引：稠密索引、分块索引、倒排索引。

稠密索引
在线性索引中，将数据集中的每个记录对应一个索引项，且索引项是按照关键码有序的排列。因此可以使用折半、插值、斐波那契等有序查找法，提高效率，但是空间代价比较高。
分块索引
将数据集的记录分成了若干块，并且这些块需要满足两个条件：
- 块内无序
- 快间有序
因此，查找分为两个步骤进行：①在分块索引表中查找关键字所在的块；②在相应的块中顺序查找关键码。分块索引普遍被用于数据库查找等技术的应用当中。
倒排索引

5. 树查找

二叉排序树
AVL树
红黑树
B/B+树

关于树查找请参考：树

6. 哈希查找

定义
在记录的存储位置和其关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。其中，f为哈希函数，记录存储的连续的存储空间称为哈希表。
查找步骤
- 存储时，通过哈希函数计算哈希地址，并存储
- 查找时，通过哈希函数计算哈希地址，并访问
哈希函数
好的哈希函数的原则：计算简单、哈希地址分布均匀
- 直接定址法
- 数字分析法
- 平方取中法
- 折叠法
- 除留余数法
- 随机数法
处理哈希冲突的方法
两个关键字key1 ≠ key2，但是却出现f(key1) = f(key2),称这种现象为冲突。解决冲突的方法有：
- 开放定址法
  一旦发生了冲突，就去寻找下一个空的散列地址
- 再散列函数法
- 链地址法
- 公共溢出区法
实现

7. 参考

大话数据结构 ---- 程杰

查找