查找

查找是指在一批数据中决定某数是否存在。有两张情况：

一种情况是对无序数据的查找，采用的是“顺序查找法”，必须在所有数中按位置一一比较，来判断参与比较的数是否为所找的数，效率较低；

另一种情况是：在排好顺序的一批数中进行查找，由于数的有序性，查找效率较高。

折半查找法，既是其中一种。

折半查找法的基本思想：选定这批数中居中间位置的一个数与所查数比较，看是否为所找之数，若不是，利用数据的有序性，可以决定所找的数在选定数之前还是在之后，从而可以很快将查找范围缩小一半。以同样的方法在选定的区域中进行查找，每次都会将查找范围缩小一半，较快便能找到目的数。

具体代码如下：

#include "stdio.h"
#define M 10

void main()
{ int a[M]={-12,0,6,16,23,56,80,100,110,115};
  int n,low,mid,high,found;
  low=0;
  high=M-1;
  found=0;
  printf("Input a mumber to be searched:");
  scanf("%d",&n);

  while(low<=high)
  { mid=(low+high)/2;
    if(n==a[mid])
    {found=1;
     break;
    }
    else if(n>a[mid])
            low=mid+1;
         else high=mid-1;
   }

    if(found==1)
    printf("the index of %d is %d",n,mid);
    else
    printf("There is not %d",n);

    getch();
}