小浣熊做单网站,90设计网账号,民治制作网站,网站制作模板网站Description
给出一个队列和要查找的数值#xff0c;找出数值在队列中的位置#xff0c;队列位置从1开始
要求使用折半查找算法
Input
第一行输入n#xff0c;表示队列有n个数据
第二行输入n个数据#xff0c;都是正整数#xff0c;从小到大#xff0c;用空格隔开
…Description
给出一个队列和要查找的数值找出数值在队列中的位置队列位置从1开始
要求使用折半查找算法
Input
第一行输入n表示队列有n个数据
第二行输入n个数据都是正整数从小到大用空格隔开
第三行输入t表示有t个要查找的数值
第四行起输入t个数值输入t行
1 n, t 10000
Output
每行输出一个要查找的数值在队列的位置如果查找不成功输出字符串error
Sample
Input
8
11 22 33 44 55 66 77 88
3
22
88
99Output
2
8
error解题思路
这道题核心思想是二分查找算法
int BinarySearch(int target, int l,int r)
{//先判断左右边界是否有问题if (target arr[r])return 0;else if (target arr[l])return 0;while (l r){int mid lr1;//左区间为[1,mid]右区间为[mid1,r]if (arr[mid] target) return mid;//若没有找到则不断二分压缩数组else if (arr[mid] target) r mid;else l mid 1;}return arr[l]target?l:0;
}AC代码
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N 10010;
int arr[N];int BinarySearch(int target, int l,int r)
{//先判断左右边界是否有问题if (target arr[r])return 0;else if (target arr[l])return 0;while (l r){int mid lr1;//左区间为[1,mid]右区间为[mid1,r]if (arr[mid] target) return mid;//若没有找到则不断二分压缩数组else if (arr[mid] target) r mid;else l mid 1;}return arr[l]target?l:0;
}
int main()
{int n;cin n;for (int i 1; i n; i) {cin arr[i];}int t;cin t;while (t--){int x;cin x;int ret BinarySearch(x, 1, n);if (ret)cout ret endl;else cout error endl;}return 0;
}
