#创作计划# 二分查找精讲

༺ཌༀ™☯追光·少年☯™ༀད༻

2025-10-20 17:06:13

发布于：浙江

9阅读

0回复

0点赞

$——————————————这是本人写的第一期周记，呸，是创作计划——————————————$

前言：

可能更好的学习体验？

本贴分为：

1，思路讲解

2，基础框架

3，真题演练

#1，思路讲解

问：100个数字里A想一个数字你怎样能最快的用方法说出A想的数字（猜数字）（此处表达不清楚，求大佬帮助）
一般错误：乱猜一"通"，靠玄学，如： $1$ ， $100$ ， $2$ ， $98$ ……
二分查找：100/2=50，所以先猜50;猜完之后会有两种情况：1，如果大了朝50/2推（一个一个判断下去）。 2，如果小了朝50/2+50推（同上）。
本蒟蒻觉得：二分所谓就是一个物品切一刀，判断，搞出切，切，切的形式。

#2，基础框架

$反正就是:$

开头：

#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long a[10000000];
//变量开全局

中部：

bool go(long long mid){
    //示例：
    /*long long sum=0;
    for(int i=1;i<=n;i++){
        sum+=min(mid,a[i]);
    }
    return sum<=m;
    */
    //这块 要按情况变化
}
int come(long long l,long long r){
    long long lll=0;
    while(l<=r){
        long long mid=(l+r)/2;
        if(go(mid)){
             //这块 也要按情况变化
            lll=mid;
        }
        else{
             //这块 也要按情况变化
        }
    }
    return lll;
}

尾部，int main函数，主函数

int main(){
    cin>>n>>m;
    long long mx=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mx+=a[i];//mx也要按题目变
    }
    long long l=,r=;//l,r要按题目变，因为：题目百变，其意自现
    cout<<come(l,r);
    return 0;//好习惯，对了，函数名可自定哟~~别嫌我唠叨，please
}

大概是这样一个框架

#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long a[10000000];
bool go(long long mid){
    return ;
}
int come(long long l,long long r){
    long long lll=0;
    while(l<=r){
        long long mid=(l+r)/2;
        if(go(mid)){
            ;
            lll=mid;
        }
        else{
            ;
        }
    }
    return lll;
}
int main(){
    cin>>n>>m;
    long long mx=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];

    }
    long long l=0,r=;
    cout<<come(l,r);
    return 0;
}