1、数组实现二分查找:
int left = 0,right = n - 1;
int find = n;//find标记找到的位置,初始化为n,表示没找到
while(left <= right){
int mid = (left + right) / 2;
if(a[mid] == x){//找到了,就标记位置,并退出循环
find = mid;
break;
}
if(x < a[mid]) right = mid - 1;//x只能在左半部分
if(a[mid] < x) left = mid + 1; //x只能在右半部分
}
if(find != n) printf("%d\n",find);
else printf("not find\n");
2、递归实现二分查找:
#include<iostream>
using namespace std;
int win,g[101];
int binsearch(int left,int right){
if(left <= right){
int mid = (left + right) / 2;
if(g[mid] == win) return mid;//找到
if(win < g[mid]) return binsearch(left,mid - 1);//在左半部分
if(win > g[mid]) return binsearch(mid + 1,right);//在右半部分
}
else return 0;//没找到
}
int main(){
int n,i,f,left,right,mid;
scanf("%d",&n);
for(i = 1; i <= n; i++) scanf("%d",&g[i]);
cin >> win;
f = binsearch(1,n);
cout << f <<endl;
return 0;
}