二分法的原理及其应用举例

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

首先,什么是二分法:

        最简单的例子就是类似于二分查找的用法来实现快速查找有序区间内的给定的目标值是否存在,当然,这也可以应用在别的问题中,二分查找是一个时间效率极高的算法,尤其是面对大量的数据时,其查找效率是极高,时间复杂度是log(n)。如果问题是单调的,且求解精确解的难度很高,可以考虑用二分法。
主要思想就是不断的对半折叠,每次查找都能除去一半的数据量,直到最后将所有不符合条件的结果都去除,只剩下一个符合条件的结果。

二分法看似简单,实则在细节上非常容易出错,要注意终止边界,左右区间开闭情况,避免漏掉答案和陷入死循环,在了解了最简单的基本原理之后,我们来由简入繁地以题目来入手理解这个算法,

1.关键的mid的处理

在整个二分法中,对于mid的处理至关重要,如果取值不当,while很容易会死循环,我们来分三点讨论这个问题:

1.1left=mid+1能否写成left=mid?

     在实数二分中,确实是left=mid,right=mid,但是在整数二分中存在取整问题,如果取left=mid,会造成原来的left和right值不改变,所以while循环会一直进行下去造成死循环,取left=mid+1则不会。

1.2 不同问题下的mid取值问题

    我们要根据不同的问题来识别到底需要左中位数还是右中位数,即对于mid的取值,我们可以向上取整同样的也可以向下取整,要看具体问题的逻辑,我们一般的都使用左中位数,即靠近left的那个数;

1.3谨慎使用(left+right)/2

我们都知道,除法的取整会导致在正负区间左右的中位数计算不一致,虽然一般的情况下,left和right都是正数,在实际计算中,我们可以用mid=left+(right-left)/2或者是mid=(left+right)>>1来替换即可,综合来看,还是(left+right)>>1更优。

下面我们还是来通过例题理解这些知识:

例题一

经典的最大值最小化模型

二分法在生活中的实际应用,数据结构与算法,数据结构

 二分法在生活中的实际应用,数据结构与算法,数据结构

 首先,我们怎样把二分法应用到这个题的求解中,我们知道这个题其实就是想让我们在划分的数组中求出无论怎样划分,其每个分子数组产生的和都有一个确定的最小值,而这个最小值一定介于原数组中的最大的一个元素(最小划分为一个数组)和原数组的所有数组元素的和(最大的一个分组)之间,我们可以在这两个边界之间枚举我们的最大值,采用二分法来寻找最小的那一个数。

我们在代码中来解释细节问题

#include <cstdio>
#include <algorithm>
int n, m;
int l, r, mid, ans;
int a[100010];
//二分答案,枚举出一个最大值,根据分组情况调整最大值,求出最优最大值。
/*
 * check 函数
 * 作用:
 *		根据枚举出的最大值,来分组,根据分出的组数来调整最大值
 * 变量:
 *		x : 枚举出的最大值
 *		sum : 分组时每组的和
 *		count : 分出的组数
 */
bool check(int x)
{
    int sum=0, count=0;//t2: 组数 t1: 每组的和
    for(int i=0; i<n; i++){
        if(sum+a[i]<=x)sum+=a[i]; //如果还是小于mid,就继续加上去
        else //objective 1如果当前sum已经达到当前最大值应该怎么处理?
        {
		  sum=a[i]; //设置sum为当前数字,相当于换入下一组
		  count++;
        }
    }
   if(count>=m)return true;//objective 2 
   return false;
}
int main()
{
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++){
		scanf("%d", &a[i]);
                r += a[i];
		l = std::max(l, a[i]);
	}
    while( l<=r ){
        mid=(l+r)/2;
        if( check(mid) )l=mid+1;//如果最后的count是大于m的话,说明mid太小了,需要l往右移
        else {//否则就是mid太大了
			r=mid-1;
		}
    }
    printf("%d",l);
    return 0;
}

重点其实就在于思路上如何将其与二分法结合在一起考虑问题。

例二

差分数组+二分

二分法在生活中的实际应用,数据结构与算法,数据结构

 二分法在生活中的实际应用,数据结构与算法,数据结构

 我们的注释在题解中见

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
/*
 * line : 原数列
 * l, r, d, : 题目要求的 对于每个区间的左端点 右端点 值
 * change : 差分数组
 * 题解:对采用的订单数进行二分,每次用差分数组优化处理当天需要的教室数并与当天可对外借出的教室数比较检验。-Megumin
 */

int line[1000010], l[1000010], r[1000010], d[1000010], change[1000010];
int n, m;

int check(int x)
{
	memset(change, 0, sizeof(change));

	for (int i = 1; i <= x; i++)
	{
		change[l[i]] += d[i];
		change[r[i] + 1] -= d[i];
		//obj 1用差分数组对前x个操作进行处理 
	}

	//for (int i = 1; i <= n; i++)
	//	change[i] += (line[i] - line[i - 1]);
	//obj 2抹平差分数组 ,此处不需要抹平差分数组,我们只需要默认为line数组全体为零,在将其和我们的change数组结合求出实际上需要的教室数量,再和原来的进行对比看看是否不够来判断非法
	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
		sum += change[i];
		if (sum>line[i])return false;
		//printf("%d ", sum);
	}
	//obj 3什么情况下是发生了问题? 

	return true;
}

int main()
{
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
		scanf("%d", &line[i]);

	for (int i = 1; i <= m; i++)
		scanf("%d %d %d", &d[i], &l[i], &r[i]);

	if (check(m))//obj 4什么情况是全都可以成立 
	{
		printf("0");
		return 0;
	}



	int left = 1, right = m, mid;
	while (left < right)
	{
		mid = (left + right) >> 1;
		if (check(mid))//obj 5	
		{
			left = mid+1;
		}
		else
		{
			right = mid;
		}
	}
	printf("-1\n");
	printf("%d", left);

	return 0;
}

当然,二分法是一个没有上限的算法,要是展开讲的话肯定是讲不完的,但是二分法的上限是如何将题目转化为二分法进行求解,又将谁二分,上下限如何确定等问题,只需要注意细节,剩下的就要靠日积月累来积累做题思维了。

例三 最小值最大问题

跳石子

二分法在生活中的实际应用,数据结构与算法,数据结构

二分法在生活中的实际应用,数据结构与算法,数据结构 

       我们的重点是在于怎么把这道题和二分法相结合起来,我们发现我们的取值范围在1~l(也就是1~终点)处,我们可以通过二分这段距离,每得到一个中间值,判断这个中间值所代表的的最短跳跃距离是不是合法,如果合法,那么我们的最短跳跃距离还在右边,于是我们把left值改为mid+1,同理,如果我们的mid值不满足,那么我们的最大值的产生一定在左边的区间内,于是将right置为mid-1;

     接着我们来思考这个判断过程,我们知道只能移走m块石头,而且我们每移走一块石头,我们的原相邻的两块石头就会变化,这样,我们可以采用类似双指针的做法来判断,具体的看代码理解:

#include <bits/stdc++.h>
#define maxn 500010
using namespace std;
int a[maxn];
int l, n, m;
inline bool check(int x)
{
	int num = 0;
	int i = 0, j = 0;
	while (i <=n)
	{
		i++;
		if (a[i] - a[j] < x)//移走当前石头的同时,j将会与第i+1个元素相邻所以下一次相比还是j
			num++;
		else
		{
			j = i;//接着找下一个
		}
		if (num > m)
			return false;
	}
	
	return true;
}
int main()
{
	scanf("%d%d%d", &l, &n, &m);
	for (int i = 1; i <=n; i++)
	{
		scanf("%d", &a[i]);
	}
	a[n + 1] = l;
	int left = 1, right = l;
	while (left <= right)
	{
		int mid = (left + right) >> 1;
		if (check(mid))
		{
			
			left = mid + 1;
		}
		else
			right = mid - 1;
	}
	printf("%d\n", left-1);
	return 0;
}

       我们总结二分法在解决实际问题的应用时,本质上我们的二分法是在确定的区间内枚举所有可能的答案,我们寻找的最大最小值,往往就在我们二分判断的结束阶段产生。

金句省身

        当你被黑暗敲打的时候,恰好证明你就是光明本身,每一个优秀的人,都会有一段沉默的时光,天赋决定下限,努力决定上限,生活给你压力,你就还它奇迹。

                                                                                                                    -----致不甘平凡的我们

二分法在生活中的实际应用,数据结构与算法,数据结构文章来源地址https://www.toymoban.com/news/detail-740048.html

到了这里,关于二分法的原理及其应用举例的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法】—二分法详解

    ①定义: 二分查找算法也称折半搜索算法,对数搜索算法,是一种在 有序数组 中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素

    2024年02月09日
    浏览(48)
  • 二分法简单题

    2024年01月24日
    浏览(53)
  • 【二分查找】一文带你掌握二分法 (附万能模板)

    一、简介 哪怕没有学过编程的同学,也许不知道二分法这个名字,但也一定接触过它的核心思想。不了解的同学也没关系,我用一句话就能概括出它的精髓: 将一个区间一分为二,每次都舍弃其中的一部分。 二分法能够极大地降低我们在解决问题时的时间复杂度。假如你要

    2024年01月19日
    浏览(54)
  • 【剑指Offer】二分法例题

    链表是数据结构中重要的一个章节,他的重要性也不言而喻,在未来不管是笔试还是面试都会遇到这类的题目,所以接下来我就会把一些链表的常考的题目全部整理出来供大家学习指正。 题目链接 描述: 给定一个长度为n的数组nums,请你找到峰值并返回其索引。数组可能包

    2023年04月13日
    浏览(44)
  • 非线性方程二分法

    优点:算法直观、简单、总能保证收敛;局限:收敛速度慢、一般不单独用它求根,仅为了获取根的粗略近似 设 f ( x ) f(x) f ( x ) 在 [ a , b ] [a,b] [ a , b ] 上连续、严格单调、满足条件 f ( a ) f ( b ) 0 f(a)f(b)0 f ( a ) f ( b ) 0 则在区间 [ a , b ] [a,b] [ a , b ] 内必有一根 x ∗ x^* x ∗ 。通

    2024年02月04日
    浏览(46)
  • 牛顿法、割线法、二分法

    牛顿法求解非线性方程组 割线法求解非线性方程组 二分法求解根号3  另外,今天上机课写程序时,发现不同的起始点可以收敛到不同的零点。也许这是一个新的值得研究的地方。 看来,计算数学也是这样,光听理论无法实现大的突破,也没法产生好的想法,必须在实践应用

    2024年02月05日
    浏览(51)
  • 06-C++ 基本算法 - 二分法

    在这个笔记中,我们将介绍二分法这种基本的算法思想,以及它在 C++ 中的应用。我们将从一个小游戏猜数字开始,通过这个案例来引出二分法的概念。然后我们将详细讲解什么是二分法以及它的套路和应用。最后,我们还会介绍 C++ STL 中的二分查找函数。让我们一起来探索

    2024年02月16日
    浏览(45)
  • 【力扣】74. 搜索二维矩阵 <二分法>

    给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非递减顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。 示例 1: 1 3 5 7 10 11 16 20 23 30 34 60 输入:matrix = [[1,3,5,7],[10,

    2024年02月15日
    浏览(39)
  • 算法:二分法---寻找H指数

    1、题目: 给你一个整数数组 citations ,其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数 。 根据维基百科上 h 指数的定义: h 代表“高引用次数” ,一名科研人员的 h 指数 是指他(她)至少发表了 h 篇论文,并且每篇论文 至少 被引用

    2024年02月08日
    浏览(44)
  • 33. 搜索旋转排序数组(二分法)

    题目要求必须设计一个时间复杂度为  O(log n)  的算法解决此问题,所以我们可以采用二分法。 Step1. 先把 nums[0] 作为目标值,通过二分法找到旋转点索引; Step2. 如果旋转点索引为0,则数组本身就是升序的,否则思想上可以将数组一分为二,看做两个升序数组。 Step3. 判断

    2024年02月05日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包