二分查找

#include<stdio.h>
#include<iostream>
using namespace std;
int main(){ 
  int a[100];//注意这里的数组下标，即a[0]=1,a[1]=2……a[99]=100
  int guess;//猜测字符
  int flag=0;//设置标志位，区分是否查找成功
  int count=0;//统计比较次数
  int low=0,mid,high=100; 
  //初始化
  cout<<"1、初始化"<<endl;
  for(int i=0;i<100;i++){
      a[i]=i+1;
  }
  cout<<"2、要查找的数字"<<endl;
  cout<<"guess:";
  cin>>guess;
  cout<<"3、二分查找"<<endl;
  //二分查找
  while(low<=high){
      count++;
      mid=(low+high)/2;
     cout<<"第"<<count<<"次查找，其中low="<<low<<"   high="<<high<<"   mid="<<mid<<endl;
     if(guess==a[mid]){
         flag=1;
         cout<<"success！比较次数:"<<count<<"次"<<endl;
         break;//查找成功就退出，如果想要继续查找也是可以的
     }
     if(guess>a[mid]){
         low=mid+1;
     }
     if(guess<a[mid]){
          high=mid-1;
     }        
  }
  if(flag==0)
      cout<<"fail！"<<endl;
}

如果暴力查找，那么时间复杂度是n；如果二分查找，每次取一半，那么最后的复杂度就是log2n。在初中接触过二分法的思想，好像是诸葛亮的聪明才智吧，这里用的也是二分法。

运行截图：

查找在数组中的元素

查找不在数组中的元素：

转载于https://blog.csdn.net/zmeilin/article/details/81139814