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;
}
