教你学c++算法题中最简单的二分，我不允许还有人不会！！！！

前段时间刷到一个视频，大概就是一整个办公室的人猜1-100中一个数字由老板给的数字，谁猜中了，就要被水球砸脑袋，要是没猜到就用这个数字把范围所小。比如答案数字是20，我第一个猜了30，比他大就变成了1-30，我再猜15，就变成了15-30

当时看着还挺乐呵的，突然看到一个弹幕飘了过去，“这不是二分吗？(doge”🤔🤔🤔

当时我就在想，二分确实可以用，可你用二分不是用最少的查找次数去找答案，那你那么快找到那个数，不就是找砸吗？😂😂😂

看来二分虽然大家都知道，可实际的用法并不太了解~那就让我来小小安利一下二分法的美丽之处吧~~~~~~

什么是二分？

顾名思义啦，就是把一堆东西一分为二，然后阿巴阿巴，直接上百度吧

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。-----------------------百度百科

怎么听着这么难呀，不急咱先提取几个关键字来看，第一个“效率高”,在前面的游戏里也和大家说了，二分查找是用非常少的次数去找到，那么具体的效率是多少呢？

答案是log₂N

假设要查找的数字范围就是游戏里的1-100，那么以2为底，2的多少次方是100呢？emmm，一二得二，二二得四，四四十六，然后三十二，然后六十四，然后就破100啦，所以最多最多只要七次，大概是2^6-2^7次方之间~~~~~

大家可能觉得并不是很快嘛，可你仔细看这个对数函数，嗷你看不到呀，那我给你贴张图来

大家可以看到x=8的时候才到3，事实上后面的增长更慢，哪怕是1024才到2的十次方，也就是说1-1024只需要找十次，就算是184****4073709551616，也只需要64次

所以这也是二分题目简单的原因之一，因为出色的效率，可以达到log级别的复杂度的算法非常少，以至于如果裸出二分题，是非常直观滴！

好了，效率分析完了之后，咱再着重的看一下啥叫顺序存储结构？

咱标题也说了c++哈，那么c++中的存储结构，最简单直接的，那就数组吧，顺序？直接排序嘛，好了，现在不就有个顺序存储结构了~~

咦，把1-100个数随机放进去排成顺序了之后不就是上面说的的游戏了吗?

对

这他*的就叫顺序！大家仔细想一想，如果我猜数字，1-100，我猜个50，然后50是随机分布的，你并不知道他大小，这你咋缩减范围呢？

二分法效率之所以高，高就高在缩减范围这一妙手！

如果还不是很了解，那我上份代码吧~

模板1：找符合条件的最小值

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

模板2：找符合条件的最大值

int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

究其本质原理，就是假设目标值在闭区间[l, r]中，每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

只不过，由于二分法在代码的实现过程中，因为缩短区间这个运算和跳出循环的判断，非常容易造成死循环，也有很多版本的二分

所以分享一个我认为非常好用，也好记的二分板子给大家！

(PS：我记模板的方法就是，在草稿中上画图，然后查看区间更新方式来决定是否要+1，推荐给大家一个方法，写完代码查会不会出问题，直接代入两个数1,2即可，百试百灵！

好了，学会了之后先来个小题目开开胃~

题目：

给定一个按照升序排列的长度为 n的整数数组，以及 q个查询。对于每个查询，返回一个元素 k的起始位置和终止位置（位置从 0开始计数）。如果数组中不存在该元素，则返回 -1 -1。

思路：

一个非常标准的二分查找题，而且已经是给出升序排列的数组，不需要自己再排列了~

所以我选择两次二分查找，也就是用我的模板，第一次找出左边界，也就是起始位置，第二次找出右边界，也就是终止位置

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int a[N];
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=0;i<n;i++)scanf("%d",&a[i]);
	while(q--){
		int k;
		scanf("%d",&k);
		int l=0,r=n-1,mid;
		while(l<r){
			mid=l+r>>1;
			if(a[mid]>=k)r=mid;
			else l=mid+1;
		}
		if(a[l]!=k){
			cout<<"-1 -1"<<endl;
			continue;
		}
		cout<<l<<" ";
		l=0;r=n-1;
		while(l<r){
			mid=l+r+1>>1;
			if(a[mid]<=k)l=mid;
			else r=mid-1;
		}
		cout<<l<<endl;
	}
}

按照传统

再来个难题压轴~~~~~

题目链接：https://ac.nowcoder.com/acm/problem/14662

题目：

小咪是一个土豪手办狂魔，这次他去了一家店，发现了好多好多（n个）手办，但他是一个很怪的人，每次只想买k个手办，而且他要让他花的每一分钱都物超所值。

即：买下来的东西的总价值/总花费=max。请你来看看，他会买哪些东西吧。

思路：

这个题目难度系数是牛客自己评的四颗星，我觉得还是挺不错的题，主要是还需要一个知识点，就是01分数规划
这道题要求单位价值（题目中的总价值/总花费），我们假设单位价值为x，我们就可以知道，x = Σv / Σc。

1）算法分析

我们已经知道了这道题是要二分，那么我们就对单位价值进二分，也就是我们要求的答案。
由上面我们设立的公式：变式可以得到 Σv - Σc * x = 0。我们在二分猜测答案的时候就以这个为基准（为什么呢？看下面）。
如果我们选取的v和c使这个式子>0的话，说明至少还有一组v和c可以使得x更大：Σv - Σc * x > 0。这就是：x < Σv / Σc（算出了答案可以比二分猜测的x大）。
所以我们就可以依照这个式子得到每个物品的权值，然后进行排序，选出最大的k个。进行Σv - Σc * x > 0的判断。

#include<bits/stdc++.h>

using namespace std;

#define int long long 
const int maxn=1e4+100;
struct node {
    int v,c,sum;
}mo[maxn];
int d[maxn],n,k;
bool cmp1(int a,int b )
{
    return a>b;
}
bool check(int x)
{
    for(int i=0;i<n;i++)
    {
        d[i]=mo[i].v-x*mo[i].c;
    }
    sort(d,d+n,cmp1);
    int d1=0;
    for(int i=0;i<k;i++) d1+=d[i];
    if(d1>=0)
        return true;
    return false;
}
signed main()    //怕炸范围，所以开了个全局定义把int换成long long
{
    int i,j,t;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        int l=0,r=1e8+1;
        for(i=0;i<n;i++)
        {
            cin>>mo[i].c>>mo[i].v;
        }
        while(l<r)    //用的第二个模板
        {
            int mid=l+r+1>>1;
            if(check(mid))
            {
                l=mid;
            }
            else 
            {
                r=mid-1;
            }
        }
        cout<<l<<endl;
    }
    return 0;
}    、、、

好啦，到此应该大家都学会了吧~

喜欢的朋友欢迎点赞收藏，有什么问题也可以评论区留言私信我哦~！

本文正在参与【[面霸养成记 ] 】征文活动，一起来聊聊校招的那些事吧，牛客周边和百元京东卡等你来领~

#笔试速成法##面试题目##C/C++#