题目描述
给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始
要求使用折半查找算法
输入
第一行输入n，表示队列有n个数据 第二行输入n个数据，都是正整数，用空格隔开 第三行输入t，表示有t个要查找的数值 第四行起，输入t个数值，输入t行
输出
每行输出一个要查找的数值在队列的位置，如果查找不成功，输出字符串error
输入样例1
8 11 22 33 44 55 66 77 88 3 22 88 99
输出样例1
2 8 error
思路分析
折半查找就是二分查找，，对于一个有序数列，通过三个位置的变换（low、mid、high），相当于部分顺序查找，只不过每次把查找的范围缩小一半。
开始先让low=0，high=n-1，mid=n/2，如果要查找的数值比mid位置的大，那么说明数值有可能在mid和high之间，那么就让low=mid 1，mid=（low high）/2，继续查找下去，如果比mid位置的小，那么说明数值有可能在low和mid之间，那么就让high=mid-1，mid=（low high）/2，继续查找下去，直到mid位置上的就是要查找的数值，或者low>high，查找结束。
AC代码
代码语言：javascript复制#include <iostream>
using namespace std;
int main() {
int n,t,target;
cin>>n;
int a[n];
for(int i=0;i<n;i )
cin>>a[i];
cin>>t;
while(t--){
cin>>target;
int low=0,high=n-1,mid=n/2;
while(low<=high){
if(a[mid]==target){
cout<<mid 1<<endl;
break;
}else if(a[mid]<target){
low=mid 1;
mid=(low high)/2;
}else{
high=mid-1;
mid=(low high)/2;
}
}
if(low>high)
cout<<"error"<<endl;
}
return 0;
}
