时间限制: 1 Sec 内存限制: 128 MB
题目描述
给出一个队列和要查找的数值,找出数值在队列中的位置,队列位置从1开始
要求使用折半查找算法
输入
第一行输入n,表示队列有n个数据
第二行输入n个数据,都是正整数,用空格隔开
第三行输入t,表示有t个要查找的数值
第四行起,输入t个数值,输入t行
输出
每行输出一个要查找的数值在队列的位置,如果查找不成功,输出字符串error
样例输入
8
11 22 33 44 55 66 77 88
3
22
88
99
样例输出
2
8
error
解决方案
#include <iostream>
#include <algorithm>
int halfSearch(const int a[], int key, int low, int high) {
if (low > high) {
return 0;
}
int mid = (low + high) / 2;
if (a[mid] == key) {
return mid;
} else if (a[mid] > key) {
halfSearch(a, key, low, mid - 1);
} else {
halfSearch(a, key, mid + 1, high);
}
}
int main() {
size_t size;
std::cin >> size;
int *p = new int[size + 1];
for (size_t i = 1; i <= size; ++i) {
std::cin >> p[i];
}
std::sort(p + 1, p + size);
size_t T;
std::cin >> T;
while (T--) {
int key;
std::cin >> key;
int flag = halfSearch(p, key, 1, size);
if (flag) {
std::cout << flag << std::endl;
} else {
std::cout << "error" << std::endl;
}
}
}