「二分搜索Binary Search」-Toy模板网

这篇具有很好参考价值的文章主要介绍了「二分搜索Binary Search」。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

0 框架

int binarySearch(vector<int> &nums, int target)
{
	int left = 0, right = ....;//right具体看情况
	while (....)
	{
		int mid = left + (right - left) / 2;//防止溢出
		if (nums[mid] == target)
		{
			....
		}
		else if (nums[mid] < target)
		{
			left = ....
		}
		else if (nums[mid] <target)
		{
			right = ....
		}
	}
	return ....;
}

二分搜索其实也是双指针，左右指针。

1 基本二分

1.1 寻找一个数

「二分搜索Binary Search」,算法,算法,数据结构,排序算法

题解

直接二分搜索解决。

Code

int binarySearch(vector<int> nums, int target)
{
	int left = 0;
	int right = nums.size() - 1;//注意
	while (left <= right)//注意
	{
		int mid = left + (right - left) / 2;
		if (nums[mid] == target)
		{
			return mid;
		}
		else if (nums[mid] < target)
			left = mid + 1;//注意
		else if (nums[mid] > target)
			right = mid - 1;//注意
	}
	return -1;
}

但是这个数有缺陷，假如有重复的数，例如[1,2,2,2,3]，想要找左边界的2，应该返回索引为1,；或者右边界的2，返回索引3，但是发现找不了，只会给你返回中间的2，返回索引2，改进在下边。

结果

「二分搜索Binary Search」,算法,算法,数据结构,排序算法

1.2 寻找左侧边界的二分搜索

Code

int left_bound(vector<int> nums, int target)
{
	if (nums.size() == 0) return -1;
	int left = 0;
	int right = nums.size();//注意,此处搜索区间其实是个左闭右开，因为nums.size()是越界了，索引的最后一个其实是要减去1的

	while (left < right)
	{
		int mid = left + (right - left) / 2;
		if (nums[mid] == target) right = mid;//搜索区间向左侧收缩，排除右边区间了，所以当发现nums[mid] == target的时候，不要直接返回，而是right = mid，再找左边界的，看左边界有没有值，实在不行，没找到，就返回mid了
		else if (nums[mid] < target) left = mid + 1;//左闭右开的区间，[mid + 1, right)，排除mid这个点了，因为mid已经搜索过了
		else if (nums[mid] > target) right = mid;//因为是左闭右开的开区间，因为要排除mid，直接等于mid即可[left, mid)，这样开区间就取不到mid了
	}
	if (left == nums.size()) return -1;
	return nums[left] == target ? left : -1;//返回left，right都可以
}

注意此处while符号变更了，改成小于号了<。那么为啥用<呢，因为首先搜索区间要包含数组的所有元素，其次，该怎么跳出while循环，当搜索区间没有元素的时候结束，那么搜索区间什么时候没有元素呢？当left = right的时候没有元素，所以这里是小于号<。

若要搜索区间变为左闭右闭的搜索区间，则稍微修改一下。

int left_bound(vector<int> nums, int target)
{
	int left = 0, right = nums.size() - 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 if (nums[mid] > target)
			right = mid - 1;//注意
	}
	// 判断 target 是否存在于 nums 中
    // 此时 target 比所有数都大，返回 -1
    if (left == nums.length) return -1;
    // 判断一下 nums[left] 是不是 target
    return nums[left] == target ? left : -1;
}

1.3 寻找右侧边界的二分搜索

Code

int right_bound(vector<int> nums, int target) {
    int left = 0, right = nums.size(); //采用左闭右开表示
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 向右边进行收缩
        } else if (nums[mid] < target) {
            left = mid + 1;//左闭右开踢mid，左边[mid + 1, right)
        } else if (nums[mid] > target) {
            right = mid;//左闭右开踢mid，[left, mid)
        }
    }
    // 判断 target 是否存在于 nums 中
	// 此时 left - 1 索引越界
	if (left - 1 < 0) return -1;
	// 判断一下 nums[left] 是不是 target
	return nums[left - 1] == target ? (left - 1) : -1;// 因为最后left = mid + 1了，所以得减去1
}

改成左闭右闭的情况。文章来源地址https://www.toymoban.com/news/detail-610904.html

int right_bound(vector<int> nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 这里改成收缩左侧边界即可
            left = mid + 1;
        }
    }
    // 最后改成返回 left - 1
    if (left - 1 < 0) return -1;
    return nums[left - 1] == target ? (left - 1) : -1;
}