首页 > 其他分享 >二分查找Binary_Search

二分查找Binary_Search

时间:2022-11-02 21:13:01浏览次数:85  
标签:二分 Binary Search int double mid 查找

 

/*Binary_Search_int.cpp*/
#include<bits/stdc++.h>
using namespace std;

/*
1、建模:划分蓝红区域,确定IsBlue()
2、确定返回l还是r
3、套用算法模板
4、(后处理...)
*/

//模板
bool check(int mid){// 检查mid是否满足某种性质
    return true;
}

int BinarySearch(int n){
    int l = -1;
    int r = n;
    int mid;
    while(l+1 != r){
        mid = r + (l-r)/2;  //防int溢出
        if (check(mid))l = mid;    //根据实际情况设计函数
        else r = mid;
    }
    return l; //根据实际情况返回l或者r
}

/*例子*/
vector<int> arr = {1,2,3,5,5,5,8,9};

int BinarySearch01(int x){
    int l = -1, r = arr.size(),mid;
    while(l+1 != r){
        mid = r + (l-r)/2;
        if(arr[mid]<x) l = mid;
        else r = mid;
    }
    return l;
}

int BinarySearch02(int x){
    int l = -1, r = arr.size(),mid;
    while(l+1 != r){
        mid = r + (l-r)/2;
        if(arr[mid]<x) l = mid;
        else r = mid;
    }
    return r;
}

int BinarySearch03(int x){
    int l = -1, r = arr.size(),mid;
    while(l+1 != r){
        mid = r + (l-r)/2;
        if(arr[mid]<=x) l = mid;
        else r = mid;
    }
    return l;
}

int BinarySearch04(int x){
    int l = -1, r = arr.size(),mid;
    while(l+1 != r){
        mid = r + (l-r)/2;
        if(arr[mid]<=x) l = mid;
        else r = mid;
    }
    return r;
}

int main(){
    cout<<BinarySearch01(5)<<endl;//找到最后一个<5的元素      输出2
    cout<<BinarySearch02(5)<<endl;//找到第一个>=5的元素       输出3
    cout<<BinarySearch03(5)<<endl;//找到最后一个<=5的元素     输出5
    cout<<BinarySearch04(5)<<endl;//找到第一个>5的元素        输出6
    return 0;
}

 

/*Binary_Search_double.cpp*/
#include<bits/stdc++.h>
using namespace std;

bool check(double x){// 检查x是否满足某种性质
} 
double bsearch_double(double l, double r){
    const double eps = 1e-6;   // eps 表示精度,取决于题目对精度的要求(英文全称为epsilon,其来源为希腊字符ε的读音)
    while (r - l > eps){
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

int main(){

    return 0;
}

 

标签:二分,Binary,Search,int,double,mid,查找
From: https://www.cnblogs.com/--OvO--/p/16852454.html

相关文章

  • ACM预备队-week2(二分)
    STO#y总#Or2二分:check函数+两模板;(前提是已经排好序才能二分)假设有一个总区间,经由我们的check函数判断后,可分成两部分,这边以o作true,.....作false示意较好识别如果我......
  • k 染色问题、二分图完美匹配数、k 路径问题
    三个知名\(\text{NP}\)问题:「\(\rm{k}\)-染色问题」「二分图完美匹配计数」「\(\rm{k}\)-路径问题」。虽然目前还没有多项式算法,但是三者都存在\(O(2^n\rm{poly}(n))\)......
  • ElasticSearch之Windows中环境安装
    ElasticSearch说明本章,我们主要以在Windows中对ElasticSearch安装进行介绍!1、......
  • 洛谷P1462spfa + 二分答案
    第一次接触二分答案的题目最开始是没有思路的看了一个题解,然后强行理解之后开始自己打了一遍,然而结果是只得了30分过了3个点其他全wa,之后是漫长的debug,这里想感慨一句自己d......
  • Arrays方法之binarySearch():二叉搜索算法搜索指定的int数组的指定值
    以下直接抄写释义:publicstatic int binarySearch(int[] a,int key)使用二叉搜索算法搜索指定的int数组的指定值。 在进行此调用之前,必须对数组进行排序(如sort(int[......
  • 二分查找
    二分查找(折半查找)前提:排好顺序的数据//元素存在返回索引,否则返回-1publicstaticintbinarySearch(int[]arr,intdata){intleft=0;intright=arr.l......
  • 京东云开发者|ElasticSearch降本增效常见的方法
    Elasticsearch在db_ranking的排名又(双叒叕)上升了一位,如图1-1所示;由此可见es在存储领域已经蔚然成风且占有非常重要的地位。随着Elasticsearch越来越受欢迎,企业花费在ES建......
  • 京东云开发者|ElasticSearch降本增效常见的方法
    Elasticsearch在db_ranking的排名又(双叒叕)上升了一位,如图1-1所示;由此可见es在存储领域已经蔚然成风且占有非常重要的地位。随着Elasticsearch越来越受欢迎,企业花费在ES......
  • UVA12003 Array Transformer(分块,块内二分)
    我们考虑用分块来水过此题我们先将原序列进行分块,对于某个块\(B\)内的数,我们把它们放进一个数组\(block[B][\]\)里,再对数组进行排序。那么我们就得到了\(\sqrt{n}\)......
  • ElasticSearch添加高亮后,文本显示不全问题
    主要原因是,需要设置高亮的片数;这里直接看最后的代码片段即可publicNativeSearchQuerygetNativeSearchQuery(ProcessLogcondition,PageParampageParam){So......