例题3.5查找（北邮复试）

例题3.4查找（哈工大复试）链接

关键字：二分查找、排序

二分查找要点：

1. 系统自带lower_bound(nums.begin(), nums.end(), targetNumber) - nums.begin();返回的>=目标值的第一个位置（可能返回的是那个大于目标值的位置，有可能序列中没有>=该数的则返回n）

2. 自写的二分查找

方法一：C++自带二分查找

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
	int n;
	while (cin >> n) {
		vector<int> a(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		int m;
		cin >> m;
		vector<int> b(m);
		for (int i = 0; i < m; i++) {
			cin >> b[i];
		}
		sort(a.begin(), a.end());

		for (int i = 0; i < m; i++) {
			int position = lower_bound(a.begin(), a.end(),b[i]) - a.begin();
			if (position == n) {
				cout << "NO" << endl;
			}  
			else if (a[position] == b[i]) {
				cout << "YES" << endl;
			}
			else if (a[position] != b[i]) {
				cout << "NO" << endl;
			}
		}
	}
	return 0;
}

方法二：自写二分查找

#include<vector>
#include<algorithm>
using namespace std;

bool BinaryFind(vector<int> nums, int target) {
	int left = 0;
	int right = nums.size() - 1;

	while (left <= right) {
		int middle = left + (right - left) / 2;
		if (nums[middle] > target) {
			right = middle - 1;
		}
		else if (nums[middle] < target) {
			left = middle + 1;
		}
		else if (nums[middle] == target) {
			return true;
		}
	}
	return false;
}

int main() {
	int n;
	while (cin >> n) {
		vector<int> a(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		int m;
		cin >> m;
		vector<int> b(m);
		for (int i = 0; i < m; i++) {
			cin >> b[i];
		}
		sort(a.begin(), a.end());
		//1. 系统自带的二分查找的写法
		//for (int i = 0; i < m; i++) {
		//	int position = lower_bound(a.begin(), a.end(),b[i]) - a.begin();
		//	if (position == n) {
		//		cout << "NO" << endl;
		//	}  
		//	else if (a[position] == b[i]) {
		//		cout << "YES" << endl;
		//	}
		//	else if (a[position] != b[i]) {
		//		cout << "NO" << endl;
		//	}
		//}
		
		//2.自己写的二分查找算法
		for (int i = 0; i < m; i++) {
			if (BinaryFind(a, b[i])) {
				cout << "YES" << endl;
			}
			else {
				cout << "NO" << endl;
			}
		}
	}
	return 0;
}