二分查找刷题

本人目前在一所普通高校研究生在读，写笔记的目的是为了记录下自己刷题的内容，方便日后观看。

参考书目：《大话数据结构》------程杰

? ? ? ? ? ? ? ? ? 《图解算法》---------袁国忠译

? ? ? ? ? ? ? ? ?《深入浅出程序设计竞赛--基础篇》------汪楚奇

本文结合《图解算法》的书作为参考，第一章涉及到二分查找的内容，再针对性的对二分查找刷题。练习的题目来源《深入浅出程序设计竞赛--基础篇》，本文将按照自己做题的思路以及书上例子的参考源码做笔记。

? ? ? ? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 图1 节选自《图解算法》

? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 图2? 节选自《深入浅出程序设计竞赛--基础篇》

?此书题目可在洛谷中查找【深基13.例1】查找 - 洛谷

此题是标准的二分查找求解，需要注意的是，当找到的目标值存在相同的元素时，要进行特殊处理，题目的要求是找到相同元素中的第一个元素的下标位置，所以找到目标函数时还要判断其是否为首位元素，用right = mid - 1; 向左搜索即可。

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

class BinarySearch
{
public:
	static int search(const vector<int>& nums, int target)
	{
		int left = 0;
		int right = nums.size() - 1;
		int result = -1; // 初始化结果为-1
		while (left <= right)
		{
			int mid = left + (right - left) / 2;
			if (nums[mid] > target)
			{
				right = mid - 1;
			}
			else if (nums[mid] < target)
			{
				left = mid + 1;
			}
			else
			{
				result = mid; // 找到一个目标值
				right = mid - 1; // 继续向左搜索第一个出现的位置
			}
		}
		// 如果找到目标值，返回索引+1（为了符合从1开始的索引）
		return result == -1 ? -1 : result + 1;
	}
};
int main()
{
	int n, m;
	cin >> n >> m;
	vector<int>nums(n);
	for (int i = 0; i < n; i++)
	{
		cin >> nums[i];
	}
	vector<int>targets(m);
	int target;
	for (int j = 0; j < m; j++) {
		cin >> target;
		// 对每个目标值调用search函数并打印结果
		cout << BinarySearch::search(nums, target) << ' ';
	}
	cout << endl;
	return 0;
}

?下面的示例是书上的代码，这个代码的缺点是没有考虑到存在相同元素的情况，需要返回的是第一个出现的位置。

#include<iostream>
#define MAXN 1000010
using namespace std;

int a[MAXN], m, n, q;
int find(int x)
{
	int l = 1, r = n;//从下标1开始
	while (l <= r)
	{
		int mid = (l + r) / 2; //查找的中间位数
		if (a[mid] == x) return mid;  //找到需要的数字
		else if (a[mid] > x) r = mid - 1; //取区间前一半
		else l = mid + 1; //取区间后一半
	}
	return -1; //没找到返回-1
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
	}
	for (int i = 0; i < m; ++i)
	{
		cin >> q;
		cout << find(q) << " ";
	}
	return 0;
}

下面是书中修改后的代码，考虑了重复元素的情况。（注：代码改变的是find函数的内容）

int find(int x)
{
	int l = 1, r = n+1;//从下标1开始,
	while (l < r)    //最后l和r会相等，左闭右开形式
	{
		int mid = l +( r-1) / 2; //查找的中间位数,避免运算溢出
		if (a[mid] >=x) r = mid; //取区间前一半
		else l = mid + 1; //取区间后一半
	}
	if (a[l] == x)return 1; //
	else return -1; //没找到返回-1
}

? ? ? ? ? ? ? ? ? ? ? ? ??图3?节选自《深入浅出程序设计竞赛--基础篇》-二分查找步骤