查找的概念

查找表(SearchTable)：相同类型的数据元素(对象)组成的集合，每个元素通常由若干数据项构成。

关键字(Key，码)：数据元素中某个(或几个)数据项的值，它可以标识一个数据元素。若关键字能唯一标识一个数据元素，则关键字称为主关键字；将能标识若干个数据元素的关键字称为次关键字。

查找/检索(Searching)：根据给定的K值，在查找表中确定一个关键字等于给定值的记录或数据元素。

◆ 查找表中存在满足条件的记录：查找成功；结果：所查到的记录信息或记录在查找表中的位置。

◆查找表中不存在满足条件的记录：查找失败。

查找有两种基本形式：静态查找和动态查找。

静态查找(Static Search)：在查找时只对数据元素进行查询或检索，查找表称为静态查找表。

动态查找(Dynamic Search)：在实施查找的同时，插入查找表中不存在的记录，或从查找表中删除已存在的某个记录，查找表称为动态查找表。

查找的对象是查找表，采用何种查找方法，首先取决于查找表的组织。查找表是记录的集合，而集合中的元素之间是一种完全松散的关系，因此，查找表是一种非常灵活的数据结构，可以用多种方式来存储。

根据存储结构的不同，查找方法可分为三大类：

① 顺序表和链表的查找：将给定的K值与查找表中记录的关键字逐个进行比较，找到要查找的记录；

② 散列表的查找：根据给定的K值直接访问查找表，从而找到要查找的记录；

③ 索引查找表的查找：首先根据索引确定待查找记录所在的块，然后再从块中找到要查找的记录。

查找方法评价指标

查找过程中主要操作是关键字的比较，查找过程中关键字的平均比较次数(平均查找长度ASL：AverageSearchLength)作为衡量一个查找算法效率高低的标准。ASL定义为：

< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PC9wPgo8cD4gICAgICAgxuTW0KO6PC9wPgo8cD4gICAgICAgICAgICAgIFBpo7qy6dXStdppuPa8x8K8tcS4xcLKo6yyu8qn0ruw49DUo6zIz86qsunV0sO/uPa8x8K8tcS4xcLKz+C1yKOsvLRQMT1QMj2hrT1Qbj0xL24go7s8L3A+CjxwPiAgICAgICAgICAgICAgQ2mjurLp1dK12mm49rzHwrzQ6NKqvfjQ0LHIvc+1xLTOyv2hozwvcD4KPGJyPgo8cD48YnI+CjwvcD4KPGgxPtK7oaK+ssyssunV0jwvaDE+CjxwPjxicj4KPC9wPgo8aDI+MS7Ls9DysunV0jwvaDI+CjxwPjxicj4KPC9wPgo8cD48L3A+CjxwPjEuMSAgsunV0su8z+s8L3A+CiAgICAgICC007HttcTSu7bLv6rKvNbwuPa9q7zHwry1xLnYvPzX1rrNuPi2qEsmIzIwNTQwO7340NCxyL3Po6zI9MSzuPa8x8K8tcS52Lz819a6zbj4tqhLJiMyMDU0MDvP4LXIo6yy6dXSs8m5pqO7t/HU8qOsyPTJqMPozerV+7j2se2jrMjUyLvDu9PQ1dK1vc/g06a1xLzHwryjrNTysunV0sqnsNyhozxicj4KPHA+PGJyPgo8L3A+CjxwPjEuMiAgyr7A/To8L3A+CjxwPjxicj4KPC9wPgo8cD48aW1nIHNyYz0="https://www.cppentry.com/upload_files/article/49/1_gpvnp__.jpg" alt="\">

1.3 实例代码:

#include 
  
   
#include 
   
     #define N 15 int SearchFun(int a[],int n,int x) { int i,f = -1; for (i = 0; i
    
     
 运行结果: 
      
      
  
     
  
     2. 折半查找(Binary Search) 
     
  
      
      折半查找又称为二分查找，是一种效率较高的查找方法。





 
      前提条件：查找表中的所有记录是按关键字有序(升序或降序) 。 查找过程中，先确定待查找记录在表中的范围，然后逐步缩小范围(每次将待查记录所在区间缩小一半)，直到找到或找不到记录为止。
     
 
     
  
     2.1 查找思想 
      
      用Low、High和Mid表示待查找区间的下界、上界和中间位置指针，初值为Low=1，High=n。 
      ⑴ 取中间位置Mid：Mid= (Low+High)/2 ； 
      ⑵ 比较中间位置记录的关键字与给定的K值： 
      ① 相等：查找成功； 
      ② 大于：待查记录在区间的前半段，修改上界指针：High=Mid-1，转⑴； 
      ③ 小于：待查记录在区间的后半段，修改下界指针：Low=Mid+1，转⑴； 
      直到越界(Low>High)，查找失败。 
     
 
     2.2举例 
      
      如图(a)，(b)所示: 
     
  
     
  
     
  
     
  
     
  
     2.3 实例代码: 
      
     #include 
      
       
#include 
       
         #define N 15 void QuickSort(int *arr,int left,int right) //快速排序算法 { int f,t; int rtemp,ltemp; ltemp = left; rtemp = right; f = arr[(left + right)/2]; //确定分界值 while (ltemp < rtemp) { while (arr[ltemp] < f) { ++ltemp; } while (arr[rtemp] > f) { --rtemp; } if (ltemp <= rtemp) { t = arr[ltemp]; arr[ltemp] = arr[rtemp]; arr[rtemp] = t; --rtemp; ++ltemp; } } if (ltemp == rtemp) { ltemp++; } if (left < rtemp) { QuickSort(arr, left, ltemp-1); } if (left < rtemp) { QuickSort(arr, rtemp+1, right); } } int SearchFun(int a[],int n,int x) //折半查找 { int mid,low,high; low = 0; high = n - 1; while (low <= high) { mid = (low + high)/2; if (a[mid] == x) return mid; else if(a[mid] > x) high = mid -1; else low = mid + 1; } return -1; } int main(int argc, const char * argv[]) { // std::cout << "Hello, World!\n"; int x,n,i; int shuzu[N]; srand(time(NULL)); printf("折半查找算法演示!\n"); printf("排序前:\n"); for (i = 0; i
        
         
 运行结果: 
          
          
  
         
  
         二、动态查找 
         
  
         动态查找可参考  
          c/c++常用算法 -- 数据结构. 
          
          
          
  
          
          
          参考书籍:《C/C++常用算法手册》 《数据结构-清华大学严蔚敏》