蓝桥杯算法日记|2.11二分算法

二分法是一种在有序数组中查找某一特定元素的搜索算法。二分法的基本思想是：每次将区间缩小一半，重复这个过程，直到找到目标值或者确定目标值不存在于该区间内。

整数二分、浮点二分、二分答案

退出条件：l、r相邻时候退出

#include <iostream>
using namespace std;
int main()
{
  // 请在此输入您的代码
  int data[200];
  for(int i=0 ; i < 200 ;i ++)data[i] = 4 * i + 6;
  int x;cin>>x;
  //二分法
  int l=0,r=199;
  while(l+1!=r){
    int mid=(l+r)/2;
    if(data[mid]>x){r=mid;}
    else l=mid;
  }
  cout<<l<<'\n';

  return 0;
}

答案取的是L；

浮点二分是在一个实数区间找一个数。实数区间可能会用f（x）一个函数来表示，判断条件是l，r非常接近，通常设置一个非常小的数sta=1e-6；

二分答案需要寻找单调函数，将它二分。将答案二分。

裂开了，，，，明天继续研究

//#include <iostream>
//using namespace std;
//int a[N];const N=5e4+5;
给了一个全程距离
//int check(int min){
//int res=0;//移走的石头数量
//for(int i=1;last=0;i<=N;i++){
//  if(a[i]-a[last]<mid){res++;continue;}
//  last=i;
//}
//return res;
//}
//int main()
//{
//  // 请在此输入您的代码
//  //最短跳跃距离尽可能长，最多移走M
//  int L,n,M;cin>>L>>n>>M;
// 
//  for(int i=0;i<n;i++){cin>>a[i];}
//  //for(int i=1;i<N;i++){b[i]=a[i]-a[i-1];}sort(b+1,b+1+N);
//  //求最短跳跃距离的max
//  //把最短跳跃距离写成check（）函数,返回移走的岩石的数量
//  //1\先按照模板，把答案的得出写下来；
//  int l=0;r=n;
//  while(l+1!=r){
//    mid=(l+r)/2;
//    if(check(mid)<=M){l=mid;}
//    else r=mid;
//    }
//  }
//  cout<<r<<'\n';
//
//  return 0;
//}

#include <iostream>
using namespace std;
const int N=5e4+9;
int a[N],L,n,m;
int check(int mid){
  int res=0,last=0;
  for(int i=1;i<=n;i++){
    if(a[i]-a[last]<mid){res++;continue;}
    last=i;
  }
  if(L-a[last]<mid)return m+1;
  return res;
}
int main(){
  cin>>L>>n>>m;
  for(int i=1;i<=n;i++){cin>>a[i];}
  long long l=0,r=1e5+5;
  while(l+1!=r){
    long long mid=(l+r)/2;
    if(check(mid)<=m)l=mid;
    else r=mid;
  }
  cout<<l<<'\n';
    return 0;
}

2.11
分查找数组元素https://www.lanqiao.cn/problems/1389/submissions/67ab4a893b64c2ee8fae7d8d/
跳石头
https://www.lanqiao.cn/problems/364/submissions/67ab64528f5ada1189f76423/【还没研究明白】