查找

1.基本概念

1.查找

在数据集合中寻找满足某种条件的数据元素的过程称为查找

2.查找表

用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成

3.关键字

数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的

4.常见操作

1）查找符合条件的数据元素

2）插入、删除某个数据元素

只需要进行操作1，静态查找表，也要进行操作2，动态查找表（除了关注查找速度，也要关注插入、删除是否方便实现）

5.算法性能评价

1、查找长度：在查找运算中，需要对比关键字的次数称为查找长度

2、平均查找长度ASL：所有查找过程中进行关键字的比较次数的平均值。

2.顺序查找

1.算法思想

又称为线性查找，通常用于线性表

2.代码实现

typedef struct{
  int *data;
  int Tablelen;
}SSTable;

//顺序查找
int Search_Seq(SSTable ST, int key){
  int i;
  for(i = 0; i < ST.Tablelen && ST.data[i] != key; ++i);
  return i == ST.Tablelen ? -1 : i;
}

3.性能分析

1、查找成功：平均查找长度 (n + 1)/2

2、查找失败：平均查找长度 n + 1

3、时间复杂度O(N)

4.优化

1、如果线性表是有序的情况，可以通过折半提高效率

2、对于有序的线性表，如果查找失败，且当前节点大于要查找的节点，则没必要继续往下查找，因此查找长度为 n/2 + n/(n + 1)

图片说明

3、查找效率需要考虑实际的应用场景

3.折半查找

1.算法思想

又称二分查找，仅适用于有序的顺序表

2.代码实现

//折半查找
int Binary_Search(SSTable L, int key){
  int low = 0, high = L.TableLen - 1,mid;
  while(low <= high){
    mid = low + (high - low)/2;
    if(L.data[mid] == key){
      return mid;
    }
    else if(L.data[mid] > key){
      high = mid - 1;
    }
    else{
      low = mid + 1;
    }
  }
  return -1;
}

3.性能分析

图片说明

判定树的形态，主要取决于mid是向上取整还是向下取整，上图为向下取整

树高 h = log2(N + 1)

时间复杂度 log2N

4.分块查找

1.算法思想

1、特点：块内无序、块间有序

图片说明

2、分块查找，又称索引顺序查找，算法过程如下：

1）在索引表中确定待查记录所属的分块（可顺序，可折半）

2）在块内顺序查找（块内是乱序的，所以只能顺序查找）

2.查找效率分析ASL

图片说明

5.B树

1.m叉查找树

//5叉排序树的结点定义
struct Node{
  int keys[4];                            //最多4个关键字
  struct Node *child[5];        //最多5个孩子
  int num;                                    //当前结点中存在几个关键字
};

1.在m叉查找树中，如果每个结点中关键字太少，会导致树变高，要查找更多层结点，效率低

2.为了避免上述问题，规定除了根节点外，任何节点至少有 m/2 个分支，即至少包含 m/2 - 1个关键字（此处的除法均采取向上取整）；如5叉排序树中，除关键字外，至少有3个分叉，2个关键字

3.为了避免多叉查找树的不平衡导致查找效率降低的问题，规定任何一个节点，其所有子树的高度都要相同

4.满足以上条件的树是B树