教你学c++算法题中最简单的二分，我不允许还有人不会！！！！
前段时间刷到一个视频，大概就是一整个办公室的人猜1-100中一个数字由老板给的数字，谁猜中了，就要被水球砸脑袋，要是没猜到就用这个数字把范围所小。比如答案数字是20，我第一个猜了30，比他大就变成了1-30，我再猜15，就变成了15-30
当时看着还挺乐呵的，突然看到一个弹幕飘了过去，“这不是二分吗？(doge”🤔🤔🤔
当时我就在想，二分确实可以用，可你用二分不是用最少的查找次数去找答案，那你那么快找到那个数，不就是找砸吗？😂😂😂
看来二分虽然大家都知道，可实际的用法并不太了解~那就让我来小小安利一下二分法的美丽之处吧~~~~~~
什么是二分？
顾名思义啦，就是把一堆东西一分为二，然后阿巴阿巴，直接上百度吧
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。-----------------------百度百科
怎么听着这么难呀，不急咱先提取几个关键字来看，第一个“效率高”,在前面的游戏里也和大家说了，二分查找是用非常少的次数去找到，那么具体的效率是多少呢？ 答案是log2N
假设要查找的数字范围就是游戏里的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;
}
} 按照传统
再来个难题压轴~~~~~
题目：
小咪是一个土豪手办狂魔，这次他去了一家店，发现了好多好多（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;
} 、、、 好啦，到此应该大家都学会了吧~ 
查看11道真题和解析