投稿
  1. 首页
  2. 随笔

最简单算法？二分算法的万字详解（上）+图解

fluent论坛 • 2022-12-17 • 随笔 • 阅读 73

最简单算法？二分算法的万字详解（上）+图解,第1张

最简单算法？二分算法的万字详解（上）+图解

目录

 

二分算法概念：

第一类：

（1）二分查找

1：溢出问题

 2：运行原理

3：注意特殊情况

小总结：

（2）X的平方根

特殊情况之一：初始化问题

特殊情况之二：是除法而不是乘法

 （3）搜索旋转排序数组

第一个if的原理：

第二个if原理：

第二类：

与第一类模板的区别：

（1）第一个错误的版本

画图！

小总结：细节决定成败！

（2）寻找峰值

（3）寻找排序数组的最小值

总结：

二分算法概念：

成功的二分查找的 3 个部分

二分查找一般由三个主要部分组成：

预处理 —— 如果集合未排序，则进行排序。

二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。

后处理 —— 在剩余空间中确定可行的候选者

转自力扣

第一类： （1）二分查找

模板 #1 是二分查找的最基础和最基本的形式。这是一个标准的二分查找模板，大多数高中或大学会在他们第一次教学生计算机科学时使用。模板 #1 用于查找可以通过访问数组中的单个索引来确定的元素或条件。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/binary-search/xe5fpe/
来源：力扣（LeetCode）

1：溢出问题

正确写法：int mid=left+(right-left)/2;

一般错误写法： int mid=(left+right)/2;

tips：写成将/2写成 >>1能提高运行效率,左移一位相当于除于2

究极好的写法：int mid=left+((right-left)>>1);

 解释：

//假定
left = 200;
right = 250;

//则left+right =450 > 255，此时已经溢出了
//0001 1100 0010 因为只能存储8位，实际1100 0010=194
mid = (left+right)/2;  //此时实际mid=194/2

mid = left+(right-left)/2; //200+(250-200)/2 = 225
//此方法绝对不会溢出，最好写成这样

作者：plainchn
链接：https://leetcode-cn.com/leetbook/read/binary-search/xe5fpe/?discussion=FevRY1
来源：力扣（LeetCode）

 2：运行原理

（1）初始化：将left指针指向数组的第一个位置，将right指向最后一个位置

（2）迭代条件：当left指针<=right指针时

（3）迭代过程：首先算出mid，然后根据mid与target的三种大小情况分类

if (nums[mid] == target)//当nums[mid]==目标值时
{
	return mid;//返回对应下标
}
else if (nums[mid] > target)//当nums[mid]>目标值时
{
	right = mid - 1;//证明目标值在mid的左边
	//则把right指针拉到mid-1的位置来压缩区间
}
else//与上相反
{
	left = mid + 1;
}
3：注意特殊情况

如果数组为空，则无需进入循环内

if (nums == NULL || numsSize == 0)
    {
        return -1;
    }

 完整代码+接口main(C C++)

#include
int search(int* nums, int numsSize, int target)
{
	if (nums == NULL || numsSize == 0)
	{
		return -1;
	}
	int left = 0;
	int right = numsSize - 1;
	while (left <= right)
	{
		int mid = left + (right - left) / 2;
		if (nums[mid] == target)
		{
			return mid;
			break;
		}
		else if (nums[mid] > target)
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}
	return -1;
}
int main()
{
	int nums[] = { 2,9,11,12,15 };
	int n = sizeof(nums) / sizeof(nums[0]);
	int target = 9;
	printf("%d", search(nums, n, target));

	return 0;
}
#include
#include
using namespace std;
int search(vector& nums, int target)
{
	int n = nums.size();
	if (n == 0)
	{
		return -1;
	}
	int left = 0;
	int right = n - 1;
	while (left <= right)
	{
		int mid = left + (right - left);
		if (nums[mid] == target)
		{
			return mid;
		}
		else if (nums[mid] > target)
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}
	return -1;
}
int main()
{
	vector nums;
	nums.push_back(1);
	nums.push_back(3);
	nums.push_back(5);
	nums.push_back(7);
	nums.push_back(9);
	int target = 3;
	cout << search(nums, target) << endl;

	return 0;
}
总结：好啦，其实也就这点事，我们给出一套通用的第一类的模板 
int binarySearch(vector& nums, int target){
  if(nums.size() == 0)
    return -1;

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

  // End Condition: left > right
  return -1;
}
（2）X的平方根

特殊情况之一：初始化问题

第一步初始化：不难想到right指针指向的是x，然后就是left指针指向0或1都是可以的

第二步迭代条件：还是很常规的left<=right

第三步迭代过程：不能说完全一样

tips：要考虑到特殊情况：

（1）当x=0时，直接是0

（2）当x=1时，直接是1

为什么要这样写？

因为它是另外一种方法的漏洞所在！

特殊情况之二：是除法而不是乘法

0 <= x <= 2^31 - 1

 int的储存大小就正好是2^31-1，那么如果你要求的是2^31-2(x)的平方根

就有这样的比较：if(mid*mid>x)这种情况就有mid爆了的可能，那么就无法比较出正确的答案

 所以我们在这里不用乘法而是用乘法，这一点和防溢出有着异曲同工之妙

正确写法：if(mid>x/mid)，那么我们结合特殊情况一来看，分母不能作为0

所以left和right的间隔不能太近因为mid=left+(right-left)/2，太近会导致mid=0;

考虑周全了，准备冻手把^-^

#include

int mySqrt(int x)
{
	if (x < 2)
	{
		return x;
	}
	int left = 1;
	int right = x;
	while (left <= right)
	{
		int mid = left + ((right - left) >> 1);
		if (mid = x / mid)
		{
			return mid;
		}
		else if (mid > x / mid)
		{
			right = mid - 1;
		}
		else
		{
			left = mid + 1;
		}
	}
	return right;//为什么返回的是right?：因为题目说了是向下取整
}
int main()
{
	int x = 8;
	printf("%d", mySqrt(x));

	return 0;
}
 （3）搜索旋转排序数组

 一切尽在注释中：

int search(int* nums, int numsSize, int target)
{
	int left = 0;
	int right = numsSize - 1;
	while (left <= right)
	{
		int mid = left + ((right - left) >> 1);
		if (nums[mid] == target)
		{
			return mid;
		}
		if (nums[mid] > nums[right])//如果中间值大于右指针所指的值，则可证明左边(包括mid)为递增序列
		{
			if (nums[mid] > target && target >= nums[left])//target在mid的左边，left的右边
			{
				right = mid - 1;
			}
			else//反之taget在mid的右边
			{
				left = mid + 1;
			}
		}
		else//如果中间值小于左指针的所指的值，则可证明右边(包括mid)为递增序列
		{
			if (nums[mid] < target && target <= nums[left])
			{
				left = mid + 1;
			}
			else
			{
				right = mid - 1;
			}
		}
	}
	return -1;
}

我知道这样肯定很多同学理解起来有点困难，那我们来画个图把^ ^

 是不是以为方框内外都会有序？那么你就会发现你掉进我的陷阱了

if (nums[mid] > nums[right])//如果中间值大于右指针所指的值，则可证明左边(包括mid)为递增序列
		{
			if (nums[mid] > target && target >= nums[left])//target在mid的左边，left的右边
			{
				right = mid - 1;
			}
			else//反之taget在mid的右边
			{
				left = mid + 1;
			}
第一个if的原理：

没有旋转过的数组是递增的，那么原先的nums[right]肯定是数组中的最大元素

比方说原来的数组是 0  1  2  3   4  5   6

移动一位为： 6   0  1   2   3   4   5

移动两位为： 5   6   0  1   2   3   4

移动三位为： 4   5   6  0   1   2   3

移动四位为： 3   4   5  6   0   1   2

可问题就在于我们并不知道旋转数组是移动了多少位

这时拿nums[mid]与nums[right]作比较

如果num[mid]>nums[right]，那么就证明，数组的至少最后一个数字已经移到了中间位置

既然中间位置是大的数，那么它的前面肯定是小于它的，并且递增->左边有序

反之，则可证明得，数组的最后一个元素还没有移动到中间位置，那么在中间位置的就至少是原先数组的第一个数，它后面的数字都比它大->右边有序

第二个if原理：

if(target>=nums[left] && target 这是在有序的区间里讨论的，如果target介于这个区间的两个端点值，那么因为递增的原因，它必然处于这个区间，

问题来了：为什么我不写成 target<=nums[mid]?

因为在这之上我写了if(nums[mid]==target)  return  mid;

这样更好方便讨论三种情况

接着再套用模板1即可

第二类：

模板 #2 是二分查找的高级模板。它用于查找需要访问数组中当前索引及其直接右邻居索引的元素或条件

int binarySearch(vector& nums, int target){
  if(nums.size() == 0)
    return -1;

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

  // Post-processing:
  // End Condition: left == right
  if(left != nums.size() && nums[left] == target) return left;
  return -1;
}
与第一类模板的区别：

第一类模板是：while(left<=right)

if(nums[mid]==target)  -> return  mid;

else if(nums[mid]>target)  -> right=mid-1

else (nums[mid] left=mid+1

第二类模板是：while(left

if(nums[mid]==target)  ->return mid;

else if(nums[mid]>target)  ->right=mid;

else(nums[mid]left=mid+1

ifnum[left]==target && left return left;

 力扣的一个大哥写得蛮好：

作者：Snowball

模板一实质上是分了三部分，|左半部分| + |目标值| + |右半部分|，模板二才是真正意义上的二分，分成了两部分，left + （right - left） // 2 是向下取整，也就是 |左半部分+可能的目标值| + |右半部分|，最后剩下一个元素 也就是左半部分的可能的目标值，所以才需要在最后一步判断一下剩下的这个值是不是要查找的值

链接：https://leetcode-cn.com/leetbook/read/binary-search/xerqxt/?discussion=qZh7qK
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我还是更习惯以具体例子来解释= =，上题把！

（1）第一个错误的版本

 我们首先要理解：一个常识性的问题：如果一个版本有bug，后续版本如果没有修改这个bug，那么后续的版本都有bug.

也就是说这个数组的情况是 正确版本 正确版本……第一个错误版本 错误版本 ……错误版本

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

int firstBadVersion(int n)
{
	int left = 1;
	int right = n;
	while (left < right)
	{
		int mid = left + ((right - left) >> 1);
		if (isBadVersion(mid))//坏的版本
		{
			right = mid;//则在前面一定就有坏的了，或者是自己
		}
		else//好的版本
		{
			left = mid + 1;//则差的版本一定在后面
		}
	}
	return left;
}

为什么这道题是模板二的范畴：？

因为就像上面力扣那个大哥说的，它是把区间分为了两部分（左值+目标值）+（右值）

下面是模板一和模板二的杂交体

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

int firstBadVersion(int n)
{
	int left = 1;
	int right = n;
	while (left <= right)
	{
		int mid = left + ((right - left) >> 1);
		if (isBadVersion(mid))//坏的版本
		{
			right = mid - 1;//则在前面一定就有坏的了，或者是自己
		}
		else//好的版本
		{
			left = mid + 1;//则差的版本一定在后面
		}
	}
	return left;
}

为什么这样写？

画图！

 

 

 看到了吗？left所指的正好是第一个错误的版本^ ^

小总结：细节决定成败！

对于二分我的建议是先试一下通用的版本，然后再画图感受，这样才能提高正确率

（2）寻找峰值

 解析：我们首先要明白峰值产生的条件：大于其左右两边的数

就有这样一个充分条件：当一个子区间是单调递增的，那么一定在它的右边一定存在峰值

同理，当一个子区间是单调递减的，那么在它的左边一定存在峰值

代码实现判断子区间是单增还是单减

else if (nums[mid] > nums[mid + 1])//如果是单减
        {
            right = mid;//峰值在左边
        }
        else//如果是单增
        {
            left = mid + 1;//峰值在右边
        }

 正确答案：

int findPeakElement(int* nums, int numsSize)
{
	if (nums == NULL || numsSize == 0)
	{
		return -1;
	}
	int left = 0;
	int right = numsSize - 1;
	int mid = 0;
	while (left <= right)
	{
		mid = left + (right - left) / 2;
		if (left == right)
		{
			return left;
		}
		else if (nums[mid] > nums[mid + 1])
		{
			right = mid;
		}
		else
		{
			left = mid + 1;
		}
	}
	return left;
}

错误答案：

int findPeakElement(int* nums, int numsSize)
{
	if (nums == NULL || numsSize == 0)
	{
		return -1;
	}
	int left = 0;
	int right = numsSize - 1;
	int mid = 0;
	while (left < right)
	{
		mid = left + (right - left) / 2;
		if (left == right)
		{
			return left;
		}
		else if (nums[mid] > nums[mid + 1])
		{
			right = mid-1;
		}
		else
		{
			left = mid + 1;
		}
	}
	return left;
}

错误的原因：

 画图分析：

方法1的图解

 方法二的图解：

 看到了吗？如果right跳两步，会导致越过峰值，

为什么会用第二种模板呢？因为它只有两种：单调增区间和单调减区间

核心就是模板+细节修改（图解理解）

（3）寻找排序数组的最小值

 其实这道题用遍历非常简单……

但是我们就要用二分！

使用模板二的原因：有序和无序两个区间，单调增区间和类似单调增区间

模板二：

int findMin(int* nums, int numsSize){
    int left = 0;
	int right = numsSize - 1;
	int mid = 0;
	while (left <= right)
	{
		mid = left + (right - left) / 2;
		if (left == right)
		{
			return nums[left];
		}
		if (nums[mid] < nums[right])//当中间值<最右边的值说明mid的右边包括（mid）为递增
		{
			right = mid;//最小值在左边
		}
		else//当中间值>最右边的值，说明mid的左边（包括mid）为递增区间
		{
			left = mid + 1;//最小值在右边
		}
	}
	return nums[left];
}

图解：

 错误情况：

int findMin(int* nums, int numsSize){
    int left = 0;
	int right = numsSize - 1;
	int mid = 0;
	while (left < right)
	{
		mid = left + (right - left) / 2;
		if (left == right)
		{
			return nums[left];
		}
		if (nums[mid] < nums[right])
		{
			right = mid-1;//最小值在左边
		}
		else
		{
			left = mid + 1;//最小值在右边
		}
	}
	return nums[left];
}

图解：

 没想到把，在这个情况下是对的

那么为什么会错呢？

 错误情况：

 正确情况：

 其实还是归根于right如果在数组较小的情况下，跳2步容易把目标值给跳过去

总结：

经验之谈，二分是简单，细节是魔鬼，记模板+画图理解边界，+1，-1？while()里面该不该填=号

这些都是要你自己去体会的

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5707372.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
fluent论坛 fluent论坛 一级用户组
0 0
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表（0条）

保存