二分查找。

二分查找

  主要思想（技巧）：
1.查找的数据必须是有序的。

2.在比较过程中如果比较数据(即a[mid])大于查找数据则再向递减部分查找，    否则再向递增部分查找。
3.两个端点low、和high变换时，因为mid已经比较过，所以low=mid+1；

  high=mid-1；

(先看代码和图例，再看上述思想)

图例

有数组a，有如下数据
带查找元素为4

当传参，进入f函数后

low=0；

high=length-1；

因为low<=high(0<=5)

所以进入while循环

循环内确定中间元素a[mid]，mid=(low+high)/2，即（0+5）/2=2

因为4>a[mid]，即4>a[2]，即4>3

所以low=mid+1

本次while循环结束

因为low<=high(3<=5)

所以再次进入while循环

循环内确定中间元素a[mid]，mid=(low+high)/2，即（3+5）/2=4

因为4<a[mid]，即4<a[4]，即4<5

所以high=mid-1

本次while循环结束

因为low<=high(3<=3)

所以再次进入while循环

循环内确定中间元素a[mid]，mid=(low+high)/2，即（3+3）/2=3

因为4==a[mid]，

所以返回下标mid（3）

结束

#include<stdio.h>
#define N 6//定义数据元素的长度
int f(int *a,int length,int key){
  int low,high,mid;
  low=0;
  high=length-1;
  while(low<=high){
    mid=(low+high)/2;//整除
    if(key==a[mid]){
      return mid;//找到返回数组下标
    }else{
      if(key>a[mid]){
        low=mid+1;
      }else{
        high=mid-1;
      }
    }
  }
  return -1;//找不到返回下标
}
int main(){
  int a[N]={1,2,33,45,54,66};//一组有序的数据
  int num;//用于存储返回的下标
  //参数：1.数组的地址，2.数组长度，3.待查找元素
  num=f(a,N,66);
  printf("%d\n",num);//输出返回值
  return 0;
}