数据结构——查找算法

一、顺序查找

• 顺序查找(Sequential Search)的查找过程为：从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；若在扫描整个表后仍未找到关键字和给定值相等的记录则表示查找失败。
• 顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。对于顺序存储结构查找成功时可以返回其在顺序表中的位置，对于链式存储结构在查找成功时则可以返回元素的指针，即结点所在地址。

  template 
  int SeqSearch(T a[], int n, T key)
  {
      int index = -1;
      for(int i = 0; i  
  

  • 在顺序查找(Sequence Search)表中，查找方式为从头扫到尾，找到待查找元素即查找成功，若到尾部没有找到，说明查找失败。所以说，Ci（第i个元素的比较次数）在于这个元素在查找表中的位置，如第0号元素就需要比较一次，第一号元素比较2次…第n号元素要比较n+1次。所以Ci=i。

  • 顺序查找方法查找成功的平均比较次数为(n + 1)/2，当待查找元素不在查找表中时，扫描整个表都没有找到，即比较了n次，查找失败。
  • 顺序查找的时间复杂度为O(n)。

    二、二分查找

    • 二分查找(Binary Search，折半查找)的查找过程是：从表的中间位置的记录开始，如果给定值和中间记录的关键字相等，则查找成功；如果给定值大于或者小于中间位置的记录的关键字，则在表中大于或小于中间记录的那一半中继续查找，重复查找操作，直到查找成功，或者在某一步时查找区间为空，则代表查找失败。
    • 折半查找要求线性表中的元素要按关键字有序排列，且由于每次查找都按位置进行操作，所以要求是顺序存储结构。
    • 为了标记查找过程中每一次的查找区间，使用low和high标记当前查找区间的下界和上界，使用mid标记区间的中间位置。

      template 
      int BinarySearch(T a[], int n, T key)
      {
          int low = 0;
          int high = n - 1; 
          while(low 
              int mid = (low + high) / 2;
              int midValue = a[mid];
              if(midValue  
      

      • 折半查找的时间复杂度为O(log2(N))，要比顺序查找的O(N)效率更高，但折半查找只适用于有序表，且限于顺序存储结构。

      • 对长度为n的有序表进行折半查找的判定树的高度为log2(n) + 1，log2(n)向下取整。
      • 在折半查找判定树中，某结点所在的层数即是查找该结点的比较次数，整个判定树代表的有序表的平均查找长度即为查找每个结点的比较次数之和除以有序表的长度。
      • 给11个数据元素有序表(2,3,10,15,20,25,28,29,30,35,40)采用折半查找。
        • 二叉查找判定树如下：

        • 查找成功时总会找到途中某个内部结点，所以成功时的平均查找长度为:
          • 即25查找一次，成功，10、30要查找2次，成功，2、15、28、35要查找3次，成功，3、20、29、40要查找4次，成功。
          • 不成功的平均查找长度为：
            • 内部结点都能查找成功，而查找不成功的是空的外部结点，所以到查询到2的左孩子，15的左孩子，28的左孩子，35的左孩子，3的左右孩子，20的左右孩子，29的左右孩子，40的左右孩子时，都是查找不成功的。如我要找1，比25小，转向左子树，比较一次，比10小，转左子树，2次，比2 小，转左子树，3次，此时2无左子树，所以失败。

              三、分块查找

              • 分块查找(索引顺序查找)是对顺序查找的一种改进，是一种介于顺序查找和二分查找之间的查找算法，分块查找的基本思想是：首先查找索引表，可用二分查找或顺序查找，然后在确定的块中进行顺序查找。

              • 分块查找要求表中每个块之间是有序的，即前块中最大关键字必须小于后块中的最小关键字，但块内元素的排列可无序。

              • 在分块查找中：

                • 需要建立一个索引表来划分块区域，通过定位某一块区域来查找相应信息
                • 索引表的表项包括两项内容：最大关键项、最大关键项块区域的起始地址
                • 同时索引表一定是有序的顺序表，可用顺序查找和折半查找两种方法查找索引表；
                • 而对索引表所标识的块区域中的数据是无序的，则只能使用顺序查找。

                • 分块索引信息如下：

                  // 块结构信息
                  template 
                  struct BlockInfo
                  {
                      T key;        // 索引区间的最大键值
                      int start;      // 索引区间的起始地址(下标)
                      int end;      // 索引区间的结束地址(下标)
                  };
                  

                • 分块查找算法实现如下：

                  template 
                  int BlockSearch(T array[], int arrayLen, BlockInfo blocks[], int indexLen, T key)
                  {
                      int ret = -1;
                      // 折半查找索引表，找到关键值所在分块
                      int low = 0, high = indexLen - 1;
                      int mid = (low + high) / 2;
                      while(low