欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【算法实验一】【1001】二分查找

程序员文章站 2024-03-14 20:59:17
...

二分查找

时限:1000ms 内存限制:10000K 总时限:3000ms

描述:

 

给定一个单调递增的整数序列,问某个整数是否在序列中。

输入:

 

第一行为一个整数n,表示序列中整数的个数;第二行为n(n不超过10000)个整数;第三行为一个整数m(m不超过50000),表示查询的个数;接下来m行每行一个整数k。

输出:

 

每个查询的输出占一行,如果k在序列中,输出Yes,否则输出No。

输入样例:

 

 

5
1 3 4 7 11
3
3
6
9

输出样例:

 

 

Yes
No
No

 

最开始刷题时,不太适应设置全局变量,因此用了很多动态数组,函数的参数也比较冗余,但在某些情况下也许反而有用,所以也放上来。



#include <iostream>
using namespace std;

int binary_search(int *array, int target, int low, int high) {
	int mid = -1;
	if (low <= high) {
		mid = (low + high) / 2;
		if (array[mid] < target)
			mid = binary_search(array, target, mid + 1, high);
		else if (array[mid] > target)
			mid = binary_search(array, target, low, mid - 1);
		if (array[mid] == target)
			return mid;
	}
	return mid;
}

int main()
{
	int len_of_input, len_of_target;
	cin >> len_of_input;
	int *input = new int[len_of_input];
	for (int i = 0; i < len_of_input; i++)
		cin >> input[i];
	cin >> len_of_target;
	int *target = new int[len_of_target];
	for (int i = 0; i < len_of_target; i++)
		cin >> target[i];

	for (int i = 0; i < len_of_target; i++) 
		cout << (binary_search(input, target[i], 0, len_of_input) < 0 ? "No" : "Yes") << endl;
}

 

 

相关标签: 算法设计