静态查找-顺序表的查找

一．查找的基本概念
1.定义
　　简单地说，查找 (Search) 就是确定一个已给的数据是否出现在某个数据元素集合中。
　　查找(Searching)的定义是：给定一个值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。
2.查找的结果
　　一种是查到该记录，即查找成功，此时查找的结果为给出整个记录的信息，或指出该记录在查找表中的位置；
　　另一种是查不到该记录，即查找失败，此时查找的结果可给出查找不成功的信息，或者给出一个“空”记录或“空”指针。
3.查找的方法
按查找表的结构可将查找表分为静态查找表和动态查找表两类。
（1）静态查找
　　静态查找表是指在查找过程中其结构始终不发生变化的查找表。
　　按查找表的存储方式，静态查找表分为顺序表和静态树表，顺序表又可以分为无序表和有序表两种。
（2）动态查找
　　动态查找表是指其结构在查找过程中要发生变化的查找表。
　　动态查找表则由于其结构在查找过程中要发生变化，一般都采用树表的形式。
4.平均查找长度
　　讨论各种查找算法时，常以算法的效率和存贮开销来衡量查找算法的优劣。然而，效率和存贮开销常常是相互制约的，很难两者兼顾。
　　效率只是相对的，通常把对关键字的最多比较次数和平均比较次数作为两个基本的技术指标，前者叫做最大查找长度 (Maximum Search Length ， MSL), 后者叫做平均查找长度 (Average Search Length ， ASL) 。
对 n 个记录进行查找时，平均查找长度为：
                    

ASL = Ci*Pi; i的取值从0到n-1

  其中：

    　①n是结点的个数；
   　 ②P_i是查找第i个结点的概率。若不特别声明，认为每个结点的查找概率相等，即
           p_l=p₂…=p_n=1/n
   　 ③c_i是找到第i个结点所需进行的比较次数。
  注意：
   　 为了简单起见，假定表中关键字的类型为整数：
        typedef int KeyType； //KeyType应由用户定义

 

二．顺序表的查找
记录的逻辑顺序与其在计算机存贮器中存储顺序一致的表，称为顺序表。
1.顺序查找的基本思想:
    从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。a
（1）类型说明
int maxsize ＝ 100 ；        //数据表的最大长度
typedef int KeyType       //关键字的类型
struct datalist
 ｛ KeyType key ；
  char ch ；
  //…      //其他域
 ｝；
datalist[maxsize] ；
（2）具体算法
void sequence_search(KeyType K,datalist r[],int n)
 { int i=0;
  r[n].key=K;
  while(r[i].key!=K)i++;
  if(i查找成功，该记录对应的下标为："<  else cout<<"查找失败！"< }
2. 算法分析：
(1) 在最坏的情况下，顺序查找需要比较 n 次，即 MSL ＝ n 。
(2) 假定各记录的查找机会均等，即 P i ＝ 1/n ，由于查找第 i 个记录需要比较 i 次，即 C i ＝ i ，于是有：

    ASL = (n+1)/2;

        这样，最大查找长度和平均查找长度的数量级 ( 即算法的时间复杂度 ) 均为 O(n) 。
3. 顺序查找的优点和缺点
　　优点：算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。
　　缺点：查找效率低，因此，当n较大时不宜采用顺序查找。

 

三. 有序表的查找
　　对于以数组方式存贮的记录，如果数组中各个记录的次序是按其关键字值的大小顺序排列的，则称为有序数组或有序表。
折半查找
　　对顺序分配的有序表可以采用折半查找 (Binary Search) ，又称二分查找。
1.基本思想
　　从第 1 个记录开始逐个顺序搜索，而是每次把要找的给定值 K ，与在中间位置的记录的关键字值进行比较。设有序记录数组 r 中每个记录的关键字值按升序排列为：

      r ₀. key ， r ₁.key ， r ₂.key ，…， r _m.key ，…,r _n-1.key
　　其中， n 为记录个数。当 i ＜ j 时，有 r _i.key ≤ r _j.key 。开始时，中间位置记录的序号为 m ＝ [(n ＋ 1)/2] ，相应的关键字值为 r[m].key 。将给定值 K 与 r[m] .key 比较，有三种可能的结果：
(1) K ＝ r[m].key
　　查找成功，结束查找。
(2) K ＜ r[m].key
　　由于各记录的关键字值是由小到大排列的，因此，如果要查找的记录存在，必定在有序表的左半部分。于是，对左半部分继续使用折半查找进行搜索，但搜索区间缩小了一半。
(3) K ＞ r[m].key。
　　如果要查找的记录存在，则必定在有序表的右半部分于是，对右半部分继续使用折半查找进行搜索，但搜索区间缩小了一半。
　　这样在查找过程中，搜索区间不断对分并成指数地缩小，因而查找速度明显地快于顺序查找。当最后只剩下一个记录，而且此记录不是要找的记录，则宣告查找失败。
2.折半查找的算法
void binary_search(KeyType K,datalist r[],int n,)
 { int m,low ,high,find;
  low=0;high=n-1;find=0;
  do{ m=(low+high)/2;
      if(K==r[m].key)
       { cout<<"查找成功，该记录对应的下标为："<         find=1;
       }
      else if(K         else low=m+1;
    }while((find==0)&&(low<=high));
  if(find==0)cout<<"查找失败！\n";
 }

3.折半查找性能分析
　　算法中每次将给定值 K 与中间位置记录的关键字值进行比较，最理想的情况是一次比较成功，那么，在最坏的情况下，要做多少次比较呢？进一步，当 2 k ≤ n ＜ 2 k +1 时，恒有 k ＝ [log₂ n ] ，因而 MSL 等于 [log₂ n ] ＋ 1 。这样，折半查找所需时间的数量级最多为 O(log₂ n ) 。与顺序查找所需平均时间 O (n) 相比，当 n 很大时，折半查找所需时间的数量级要小。因此，对于关键字已经有序的查找表，采用折半查找效率比较高。
4.折半查找的平均查找长度
　　折半查找的过程实际上是从二叉树的根结点开始到该记录结点的查找过程。因此，比较的次数不超过二叉树的深度 d ＝ [log₂ n ] ＋ 1 。特别地，当 n ＝ 2 ^d -1 时，描述折半查找的二叉树一定是深度为 d 的满二叉树。查找第 1 层 ( 根结点 ) 的记录仅需一次比较，且只有一个记录。查找第 i 层 (1 ≤ i ＜ d) 记录需做 i 次比较，第 i 层有 2 ^i-1 个记录。假定每个记录的查找概率相等，即 P _i ＝ 1/n ，则平均查找长度为：

ASL = Ci*Pi=1/n(C1+C2+C3+…..)=1/n(1+2*2+3*2²+…+(d-1)*2^d-2+d*L)

式中， L 为叶结点个数， 1 ≤ L ≤ 2^d-1 ， n ＝ 2^d-1－1＋L。
　　所以，折半查找的平均查找长度数量级 ( 算法时间复杂度 ) 亦为 O (log2 n ) 。
5、二分查找的优点和缺点
　　虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间。
　　二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。
　　对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找。