输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x,使用二分查找算法查找x,输出x所在的下标(0~n-1)及比较次数。若x不存在,输出-1和比较次数。

输入格式:

输入共三行: 第一行是n值; 第二行是n个整数; 第三行是x值。

输出格式:

输出x所在的下标(0~n-1)及比较次数。若x不存在,输出-1和比较次数。

输入样例:

4
1 2 3 4
1

输出样例:

0
2

考试的时候一团浆糊,这个代码明明有问题,但是我瞎调参活生生的把他调对了。。。。

 

#include<iostream>
using namespace std;
int num[1005];
int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>num[i];
	}
	int x;
	cin>>x;
	int l=0;
	int h=n-1;
	int count=0;
	int t=(l+h)/2;
	while(l!=h){
		count++;
		t=(l+h)/2;
		if(num[t]==x){
			cout<<t<<endl<<count+1<<endl;
			return 0;
		}
		if(num[t]>x){
			h=t;
		}else if(num[t]<x){
			l=t;
		}
		if(l==(h-1)){
			break;
		}
	}
	if(num[h]==x){
			cout<<h<<endl<<count<<endl;
	}else if(num[l]==x){
			cout<<l<<endl<<count<<endl;
	}else{
		cout<<-1<<endl<<count<<endl;
	}
	return 0;
}

 找了个靠谱答案

#include<iostream>
using namespace std;
extern int sum=0;

int BinarySearch(int a[],const int &x,int n)
{
    int left = 0;
    int right = n-1;
    while (left <= right)
    {
        sum++;
        int middle = (left + right)/2;
        if(x == a[middle]) return middle;
        if(x > a[middle]) left = middle + 1;
        else right = middle - 1;
    }
    return -1;
} 

int main()
{
    int n,a[1000],x,result;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    cin>>x;
    
    result = BinarySearch(a,x,n);
    cout<<result<<endl<<sum;
    return 0;

}