查找

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. 参考

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