1.名词解释

• 平均查找长度（ASL）（不是AWSL）
  查找过程中比较次数的平均值:

  ASL = \sum_{\mathclap{1\le i\le n}} P_1C_i

  其中，n为文件记录个数，Pi为第i个记录的查找概率，Ci是找到第i个记录时经历的比较次数。

2.顺序查找

• 简介
  从顺序表一端开始，逐个比较，直到查找成功。若失败，则返回-1.
• 实现

  int srh(int* a,int target)
  {
  a[0] = target; //将没有利用的数组第0位设为监视哨，这样查找失败会返回0
  for(int i = len;;i--) //len为序列中元素个数
      if(a[i] == target)
          return i;
  }

• 性能
  查找第i个元素比较次数为 n-i+1,可计算其ASL：

  ASL = \sum_{\mathclap{1\le i\le n}} P_1C_i = \frac {1}{n}\sum_{\mathclap{1\le i\le n}} (n - 1 + 1) = \frac {n + 1}{2}

3.二分

• 简介
  对一个升序序列，先比较其中间值，如果比中间值小，则对其左端序列进行同样的操作，否则对其右边的序列进行同样的操作。注意，序列必须有序。
• 实现

  int bin_srh(int* a,int target,int l,int r)
  {
  while(l <= r)
  {
      int m = (l + r) / 2;
      if(a[m] == target)
          return m;
      if(a[m] < target)
          l = m + 1;
      else
          r = m - 1;
  }
  return -1;
  }

• 性能

  ASL = \sum_{\mathclap{1\le i\le n}} P_1C_i = \frac {1}{n} \sum_{\mathclap{1\le j\le h}} 2^{j-1} j = \frac {n+1}{n}log_2(n+1)-1

4.索引查找

• 简介
  分块查找要求把一个大的线性表分解成若干块，每块中的节点可以任意存放，但块与块之间必须排序。假设是按关键码值非递减的，那么这种块与块之间必须满足已排序要求，实际上就是对于任意的i，第i块中的所有节点的关键码值都必须小于第i+1块中的所有节点的关键码值。此外，还要建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，按块的顺序存放到一个辅助数组中，显然这个辅助数组是按关键码值费递减排序的。查找时，首先在索引表中进行查找，确定要找的节点所在的块。由于索引表是排序的，因此，对索引表的查找可以采用顺序查找或折半查找；然后，在相应的块中采用顺序查找，即可找到对应的节点。（代码教材未给出不做要求，目前没用到过，故本文目前不贴代码）
• 性能

  log_2{n} \le ASL_bs \le \frac{n+1}{2}

总提纲：《数据结构》期末提纲小结