查找

一、顺序查找的基本思想：

从表的一端开始，顺序扫描表，依次将扫描到的结点关键字和给定值（假定为a）相比较，若当前结点关键字与a相等，则查找成功；若扫描结束后，仍未找到关键字等于a的结点，则查找失败。

 

说白了就是，从头到尾，一个一个地比，找着相同的就成功，找不到就失败。很明显的缺点就是查找效率低。

 

适用于线性表的顺序存储结构和链式存储结构。

计算平均查找长度。

例如上表，查找1，需要1次，查找2需要2次，依次往下推，可知查找16需要16次，

可以看出，我们只要将这些查找次数求和（我们初中学的，上底加下底乘以高除以2），然后除以结点数，即为平均查找长度。

设n=节点数

平均查找长度=（n+1）/2

 

二、二分法查找（折半查找）的基本思想：

前提：

（1）确定该区间的中点位置：mid=（low+high）/2    

min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置

（2）将待查a值与结点mid的关键字（下面用R[mid].key）比较，若相等，则查找成功，否则确定新的查找区间：

如果R[mid].key>a，则由表的有序性可知，R[mid].key右侧的值都大于a，所以等于a的关键字如果存在，必然在R[mid].key左边的表中。这时high=mid-1

如果R[mid].key则等于a的关键字如果存在，必然在R[mid].key右边的表中。这时low=mid

如果R[mid].key=a，则查找成功。

（3）下一次查找针对新的查找区间，重复步骤（1）和（2）

（4）在查找过程中，low逐步增加，high逐步减少，如果high，则查找失败。

平均查找长度=Log2(n+1)-1

 

注：虽然二分法查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算，所以二分法比较适用于顺序存储结构。为保持表的有序性，在顺序结构中插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动而又经常需要查找的线性表。

#include <stdio.h>
int binSearch(int, int, int);
main()
{
   int i, n = 10, x = 7;
   //这里如果把数组a[]定义为a[n],是错误的，不能定义变长数组。
   int a[10];
   printf("Please enter your num:/n");
   //从标准输入给数组赋值的唯一方法：用for循环
   for(i=0;i<n;i++)
   {
      scanf("%d",&a[i]);
   }
   printf("The %d can be found in the arr, it is %dth of the arr/n",
           x, binSearch(x,a,n));
}
/*第一种方法，判断都在循环内*/
int binSearch(int x, int a[], int n)
{
   int low, high, mid;
   low = 0;
   high = n-1;
   //注意，这里必须用<=, 用<不对，一直返回-1
   while(low <= high)
   {
      mid = (low + high) / 2;
      if(x < a[mid])
      high = mid - 1;
     else if(x > a[mid])
      low = mid + 1;
     else
      return mid;
   }
   return -1;
}
/*在循环内执行一次测试的方法*/
/*int binSearch(int x, int a[], int n)
{
   int low, high, mid;
   low = 0;
   high = n-1;
   mid = (low + high) / 2;
   while((low <= high)&&(a[mid]!=x))
   {
      if(x < a[mid])
      high = mid -1;
     else
      low = mid + 1;
     mid = (low + high) / 2;
   }
   if(a[mid] == x)
   return mid;
   else
   return -1;
}
*/

Please enter your num:
1
2
3
4
5
6
7
8
9
10
The 7 can be found in the arr, it is 6 th of the arr

参考资料：
http://blog.csdn.net/shan9liang/article/details/7533466
http://blog.csdn.net/zevin/article/details/6565811