前段时间刷到一个视频，大概就是一整个办公室的人猜 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）算法分析

1. 我们已经知道了这道题是要二分，那么我们就对单位价值进二分，也就是我们要求的答案。

2. 由上面我们设立的公式：变式可以得到 Σv - Σc * x = 0。我们在二分猜测答案的时候就以这个为基准（为什么呢？看下面）。

3. 如果我们选取的 v 和 c 使这个式子>0 的话，说明至少还有一组 v 和 c 可以使得 x 更大：Σv - Σc * x > 0。这就是：x < Σv / Σc（算出了答案可以比二分猜测的 x 大）。

4. 所以我们就可以依照这个式子得到每个物品的权值，然后进行排序，选出最大的 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;}    、、、

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