当前位置：首页 > article >正文

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

article 2024/9/20 23:40:41

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