查找的基本概念

1. 查找表
   由同一类型的数据元素（或记录）构成的集合
2. 两类查找表

• 静态查找表：查找的同时对查找表不做修改操作（如：插入和删除）
• 动态查找：查找的同时对查找表具有修改操作

3. 基本术语
   关键字：记录中某个数据项的值，可用来识别一个记录
   两类关键字：主关键字和次关键字
   主关键字：唯一标识数据元素
   次关键字：可以表示若干个数据元素
4. 查找算法的评价指标
   关键字的平均比较次数，也称平均搜索长充ASL(Average Search Length)
5. 查找的方法
   顺序查找、二分查找、分块查找、二叉树排序查找、平衡二叉树、B-树、B+树、散列查找

方法1️⃣ 顺序查找

应用范围：
顺序表或线性链表表示的静态查找表：
表内元素之间无序

1. 顺序表的表示

typedef struct{
  Elemtype *R; // 表基地址
  int length; // 表长
} SSTable;

2. 顺序表L中查找值为e的数据元素
   把待查关键字key存入表头（“哨兵”）从后向前逐个比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度。

int Search_Seq(SSTable ST, KeyTape key){
  ST.R[0].key=key;
  for(i=ST.length;ST.R[i].key!=key,--i);
  return i;
}

3. 顺序查找的性能分析
   空间复杂度：一个辅助空间
   时间复杂度
   查找成功时的平均查找长度
   设表中各记录查找概率相等
   ASL（n）= n+1
4. 顺序查找算法的特点
   算法简单，对表结构无任何要求（顺序和链式）
   当n很大时查找效率较低
   改进措施：二分查找，分块查找

方法2️⃣:二分查找

折半查找的前提条件是：查找表有序

1. 思想
   折半查找（Binary Search)是用待查找元素的key与查找表的“中间位置”的元素的关键字进行比较，若他们的值相等，内里查找成功，若查找元素key大于查找表的“中音位置”的元素关键字的值，则在查找表的中间位置的后端范围内，继续使用折半查找。址到查找成功或者失败为止。

2. 举例过程
   

3. 性能分析 为了分析二分查找的性能，可以用二叉树来描述二分查找过程，把当前朝着区间中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似方法，由此得到二叉树称为二分查找的判定树。

4. 算法描述
   折半查找（非递归算法）

function Search_Bin( ST,  key){
  // 若找到，则函数值为该元素在表中的位置，否则为0
  let low = 0; 
  let high = ST.length - 1;
  let mid = 0;
  while(low <= high){
    if(ST[low] == key)
      return low;
    if(ST[high] == key)
      return high;    
    mid = Math.floor(low + (high - low) / 2 ); 
    // 使用(low+high)/2会有整数溢出的问题
    //（问题会出现在当low+high的结果大于表达式结果类型所能表示的最大值时，
    // 这样，产生溢出后再/2是不会产生正确结果的，而low+((high-low)/2)
    // 不存在这个问题
    if(key == ST[mid]) {
      return mid;
    } else if (key < ST[mid]) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  if( low > high ) {
    return -1;
  }
}
let res = Search_Bin([1,2,3,4,5,6,7,8,9], 3)
console.log(res)

折半查找（递归算法）

function Search_Bin( ST, key, low, high){
  if(low > high){
    return -1;// 查找不到时返回-1
  }
  if(ST[low] == key)
    return low;
  if(ST[high] == key)
    return high; 
  mid = Math.floor((low + (high - low) / 2 ));
  if(key == ST[mid]){
    return mid;
  } else if(key < ST[mid]){
    return Search_Bin(ST, key, low, mid - 1);
  } else{
    return Search_Bin(ST, key, mid + 1, high);
  }
}
let L = [1,2,3,4,5,6,7,8,9];
Search_Bin(L, 3, 0, L.length - 1)

方法3️⃣:分块查找

分块有序，即分成若干子表，要求每个子表中的数值都比后一块中数值小（但子表内部未必有序）
然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）
分块查找（块间有序，块内无序）
👉分块查找过程

1. 对索引表使用折半查找法（因为索引表是有序表）
2. 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；
   分块查找性能分析
   查找过程：每次将待查记录所在区间缩小一半，比顺序查找效率高，时间复杂度O（log2^n）
   适用条件：采用顺序存储结构的有序表，不宜用于链式结构
   分块查找优缺点：
   优点： 插入和删除比较容易，无需进行大量移动。 缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算。
   适用情况：如果线性表既要快速查找又经常动态变化，则可采用分块查找。

方法4️⃣:树表的查找

表结构在查找过程中动态生成
对于给定值key
若表中存在，则成功返回；
否则插入关键字等于key的记录

方法1： 二叉树排序查找

二叉排序树查找：前提是将查找表组织成为一棵二叉排序树。 思想：
若二叉排序树为空，则查找失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子对重复些步骤，否则，进入右子树重复些步骤，若在查找过程中遇到二叉排序树的叶子结点时，还滑找到待找结点，则查找不成功。 二叉排序树特点：
二叉排序树是空树，或是满足如下性质的二叉树：

1. 若其左子树非空，则左子树上所有结点的值均小于根结点的值
2. 若其右子树非空，则右子树上所有结点的值均大于根结点的值
3. 其左右子树本身又各是一棵二叉排序树
   生成二叉排序树的过程：
   例如，给定关键字序列：79，62，68，90，88，89，17，5，100，120

算法思想：

1. 若二叉排序树为空，则查找失败，返回空指针
2. 若二叉排序树非空，将给定值key与根结点的关键之T->data.key进行比较
   | 1. 若key等于T->data.key,则查找成功，返回根结点地址
   | 2. 若key于小T->data.key,则进一叔查找左子树
   | 3. 若key大于T->data.key，则进一叔查找右子树
3. 二叉排序树的性能分析
   在二叉排序树查找中，成功的查找次数不会超过二叉树的深，而具有n个结点的二叉排序树的深度，最多为log2^n,最坏为n。因些，二叉排序树查找的最好的时间复杂度为O（log2^n),最坏的时间复要度为O（n），一般情况下，其时间复杂度大致可看成O（log2^n),比顺序查找效率要好，但比二分查找要差。
4. 存在问题：可退化成一个顺序表查找，效率很低

方法2：平衡二叉树

平衡二叉树查找的前提是要调整成一棵平衡二叉树。

1. 思想
   若平衡二叉树为空，则查找失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于等查值，则进入左子树重复此步骤，否则，进入右子树重复些步骤，若在查找过程中遇到平衡二叉树的叶子结点时，还没有找到待找结点，则查找不成功。
2. 举例过程
   第一步： 调整成一棵平衡二叉树
   第二步：平衡二叉树查找

平衡二叉树定义：
若一棵二叉树中每个结点的左、右子树的深度之差的绝对值不超过1，则称这样的二叉树为平衡二叉树。
平衡因子：
将该结点的左子树深度减去右子树深度的值，称为该结点的平衡因子（balancefactor)
说明：
一棵二叉排序树中，所有结点的平衡因子只能为0，1，-1时，则该二叉排序树就是一棵平衡二叉树。
第一步： 非平衡二叉树的平衡处理
若一棵二叉排序树是平衡二叉树，扦入某个结点后，可能会变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成一棵平衡二叉树。
处理的原则应该是处理与扦入点最近的、而平衡因子又比1大或比-1小的结点，下面将分四种情况讨论平衡处理。
情况1：LL型处理（左左型）
情况2：LR型处理（左右型）
情况3：RR型的处理（右右型）
情况4：RL型的处理（右左型）

平衡三叉树本身就是一棵二叉树，故它的查找与二叉排序树完全相同，但它的查找性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度O（n），它的时间复杂度与二叉排序树的最好时间复杂相同，都为O（log2^n） 平衡二叉树的查找性能优于二叉排序树
3. 平衡二叉树的查找及性能分析
平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同，但它的查找性能优于二叉排序树，不像二叉排序一样，会出现最坏的时间复杂度O（n），平衡二叉树最好最坏时间复杂相同均为O（log2n)

方法3: B-树

1. 定义：B-树是一种平衡的多路查找树
   一棵m阶的B-树或为空树，或为满足下列特性的m叉树：
   | 1. 树中每个节点至多有m棵子树
   | 2. 若根结点不是叶子结点，则至少有两棵子树
   | 3. 除根结点之外的所有非终端结点至少有[m/2]棵子树 | 4. 所有的非终端结点中包含下列信息数据（N,A0,K1,A1,...An) B- 树是一种平衡的多路查找树
   4阶B-树，每个节点最多4个指针3个关键字
   一棵m阶B-树每个节点最多有m棵子树m-1个关键字，最少有[m/2]棵子树[m/2]-1个关键字
   B-树的删除：兄弟够，低升高降。兄弟不够，拉下来合并
   

方法4: B+ 树

1. B+树是B-树变形，m阶的B+树和m阶的B-树的区别
   关键字数和子树个数一样多
   所有叶子结点中包含合部关键字信息及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。
   所有非终端结点可看成索引，节点中仅含有其子树中的最大（或最小）关键字。
   操作：B+树的查找、插入、删除
   在B+树上进行随机查找、插入和删除的过程基本上与B-树类似
   查找：若非终端结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点。因为，在B+树中，不管 查找成功与否，每次查找都是走一条从根节点到叶结点的路径。
   B+查找的分析类似于B-树。
   插入：仅在叶子结点上进行插入，当结点中的关键字个数大于m时要分裂成两个结点，他们所含关键字的个数分别为(m+1)/2向下取整和（m+1）/2向上取整。并且，他们的双亲结点应同时包含这两个结点中的最大关键字。
   删除：B+树的删除也仅在叶子结点进行，当叶子结点中最大关键字被删除时，其在非终端结点中的值可以作为一个”分界关键字“存在，若因删除而使结点中关键字的个数少于m/2向上取整时，其它兄弟结点的合并过程亦和B-树类似。

方法5️⃣:散列查找

优点：不通过 大量无效比较，直接找到待查关键字的位置的查找方法

1. Hash方法：通过函数计算存储位置
2. Hash函数：在Hash方法中使用的函数
3. Hash表：按Hash方法构造出来的表称为Hash表
4. Hash地址：通过Hash函数计算记录的存储位置，称Hash地址
5. 冲突（Collision）：不周记录的关键字经过Hash函数的计算可能得到同一Hash地址，即key1<>key2,H(key1)=H(key2)
   知识点1. 如何构造Hash函数？
   要求：对于给定的一个关键码集合，选择一个计算简单且地址分布比较均匀的Hash函数，避免或尽量减少冲突。
   知识点2. 拟定解决冲突的方案
   要求：允许冲突，但要有解决的方法
   知识点3. Hash函数的性能

知识点1：Hash函数的构造

构造Hash函数应注意以后几个问题：

1. 计算Hash函数所需时间

2. 关键字的长度

3. Hash表的大小

4. 关键字的分布情况

5. 记录的查找频率

6. 直接地址法 此类方法取记录中关键码的某个线形函数值作为 Hash地址：
   Hash(key) = a*key + b; 其中： a,b为常数
   这类Hash函数是一对一的映射，一般不会产生冲突，但是它要求Hash地址空间大小与关键码集合的大小相同，这种要求一般很难实现。

7. 除留取余法
   设Hash表中允许的地址数为m，取一个不大于m，但最接近或等于m的质数p，或选取一个不含有小于20的质因子的合数作为除数。这样的Hash函数为：
   Hash(key) = key%p（p<=m)

8. 数字分析法
   设有n个d位数，每一位可能有r种不同的符号。这r种不同的符号在各位上出现频率不一定相同。可根据Hash表的大小，选取其中各种符号分布均匀的若干位作为Hash地址。

9. 平方取中法
   先计算构成关键码的表示符的内码的平方，然后按照Hash表的大小取中间的若干位作为Hash地址。在平方取中法中，一般取Hash地址为2的某次幂。

10. 折叠法————有两种方法： 第一种：移位法把各部分的最后一位对齐相加。
    第二种：分界法是把各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当作散列地址。

11. 随机数法
    所谓随机数法（random）是指为Hash表中的关键字选取珍上随机函数值作为Hash地址。
    即 H（key）= random（key）
    其中random为随机数

知识点2：拟定解决冲突的方案

原因：散列表是一种理想的情形，即每一个关键字对应一个唯一的地址。但是有可能出现这样的情形，两个不同的关键字有可能对应同一个内存地址，这样，将导致后放的关键字无法存贮，我们把这种现象叫做冲突（collision）。在散列存贮中，冲突是很难避免的，除非构造出的散列函数为缍性函数。散列函数选得比较差，则发生冲突的可能性越大。我们把相互发生冲突的关键字互称为“同义词”。
虽然冲突不可避免，但发生冲突的可能性却与三个方面因素有关。
第一是装填因子a有关，所谓装填因子是指散列表中已存入的元素个数n与散列表的大小m的比值，即a=n/m。当a越小时，发生冲突的可能性越小，a越大（最大为1）时，发生冲突的可能性就越大。但是，为了减少冲突的发生，不能将a变得太小，这样将会造成大量存贮空间的浪费，因些biux兼顾存贮空间和冲突两个方面。
第二是与所构造的散列函数有关。
第三是与解决冲突的方法有关。

装满因子a（0.6~0.9)最佳

解决冲突的方法

1. 开放地址法
   所谓开放地址法是指在冲突发生时，产生某个探测序列，按照这个序列，探测在Hash表中的其它存储单元，直到探测不到发生冲突的存储单元为止。可以用下述公式来描述：
   Hi(key) = (H(key) + di)%m(i=1,2, ...., m) 其中：Hi(key)为经过i次探测H(key)为关键字key的直接Hash地址，m为Hash表的长度，di为每次再探测时的地址增量。这种方法容易产生“淤积（full-up）”现象。
   一般情况下，地址增量的取值有以下三种：
   di=1，2，...,m-1
   称这种情况为线性探测再Hash；
   di=1^2,-1^2,2^2,-2^2,...,+-K^2(K<=m/2向下取整)
   这种情况为二次探测再Hash： di=伪随机探测再Hash
   二次探测会跳过某些空房子
2. 链地址法
   链地址法处理冲突的方法是，将通过Hash函数计算出来的Hash地址相同的关键码通过链表链接起来，各链表表头结点组成一个向量，向量的元素个数与关键字个数相同。
3. 建立公共溢出区
   建立公共溢出区是指当冲突发生时，将这些关键字存储在另设立的一个公共溢出区中。具体的做法是：假设Hash地址区间为0到（m-1），设向量HashTable[m]为基本表，每一个分量存放一个记录，另外设一个向量OverTable[n]为溢出表。将所有与基本表中关键字冲突的记录，都存放到该溢出表中。
4. 再Hash法
   所谓再Hash法是指当冲突发生时，采用另一个Hash函数计算关键字的Hash地址。即构造一系列Hash函数H1(key),H2(key),...,Hk(key)，当冲突发生时依次检查所构造一系列的Hash函数所得到的Hash地址是否为空。这种方法不易产生“淤积”现象，但去增加了计算时间。

知识点3：Hash查找性能分析（散列查找性能分析）

散列查找按理论分析，它的时间复杂度为O(1)，它的平均查找长度为ASL=1,但实际犹豫冲突的存在，平均查找长度将会比1大。

1. 线性探查法的性能分析
   由于线性控查法解决冲突是线性地查找空闲位置的，平均查找长度与表的大小m无关，只与所选取的散列函数H及装填因子a的值和该处理方法有关，成功平均查找长充为：ASL=1/2(1+1)/(1-a)
2. 拉链法查找的性能分析
   由于拉链法查找就是在单链表上查找，查找单链表中每一个结点的次数为1，第二个结点次数为2，其余依次类推。平均查找长度为ASL=1+a/2