B : DS静态查找之折半查找

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
99

Output

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 = l+r>>1;//左区间为[1,mid]，右区间为[mid+1,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代码

#include<iostream>
#include<cstring>
#include<algorithm>
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 = l+r>>1;//左区间为[1,mid]，右区间为[mid+1,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;
}