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

二分查找

时间:2023-11-20 15:22:38浏览次数:32  
标签:二分 right target int mid 查找 left

一、二分查找介绍

首先使用二分法的前提是这个数组或者序列是排好序的。对于一个排好序的数组(升序),如果要让我们从中找一个指定的数并输出它的下标,我们可以直接暴力枚举,时间复杂度为O(n),当我们使用二分查找的时候它的时间复杂度为O(log n)

二分法的核心思想就是:每次都将查询的范围缩小一半

还是上面的例子,我们首先选择数组中间的数字和目标值进行比较,那么会有三种结果

1.相等:这种情况最好了可以直接返回答案

2.比目标值大:因为我们的数组是排好序的,那么中间的值比它大,是不是就说明目标值在它的左边,所以我们的下一步就是往左边接着二分

3.比目标值小:同理,不同点在于这次我们要往右边接着二分

代码实现:

#include<bits/stdc++.h>
using namespace std;
int main()

{
    vector<int> v = {1,5,6,8,10,82,699};
    int l = 0, r = v.size() - 1;
    int target = 5;
    while(l  < r){
        int mid = (l + r) / 2;//不用纠结数组的长度是奇数还是偶数
        if(v[mid] == target){
            cout << mid;
            break;
        }
        else if(v[mid] > target)
            r = mid;//这样查询的右边界就到了mid这里
        else
            l = mid;
    }
    
    return 0;
}

上面只是简单实现了一下,是不严谨的,但是有一点数组的长度是奇数还是偶数真的不重要!!!

二、边界

二分查找的思想是很好理解的,难的是边界的考虑。也就是上面代码中是 l < r 还是 l <= r,以及是 r = mid 还是 r = mid - 1

一般的来说有以下几种

1.左开右闭(比较少见)

2.左闭右开

3.左闭右闭

还是上面的例子,这次我们分析一下,当left == right的时候是有没有意义的以及right = ?

首先我们要确定查找的区间是什么,我们发现目标值target是在[left , right]这个区间当中的,所以当left == right的时候,它在数组中所对应的值也有可能是我们要找的值,即有意义。

然后就是right的取值,我们的判断条件是if(v[mid] > target),想一下当这个条件成立的时候是不是就说明mid所对应的值是比target大的,所以我们不需要再让right = mid而是让right = mid - 1

综上优化后的代码是:

 

#include<bits/stdc++.h>
using namespace std;
int main()

{
    vector<int> v = {1,5,6,8,10,82,699};
    int left = 0, right = v.size() - 1;
    int target = 5;
    while(left <= right){
        int mid = (left + right) / 2;
        if(v[mid] > target)
            right = mid - 1;
        else if(v[mid] < target)
            left = mid + 1;//它和right同理,只不过它是要往前走一位
        else{
            cout << mid;//找到直接输出并return
            return 0;
        }
    }
    cout << -1;//没找到就输出-1
    return 0;
}

接下来我们来看左闭右开即[left,right),首先很容易想到的是left == right是没有意义的,然后就是right的取值变化,假设right = mid - 1,根据区间的定义

right是取不到的,所以mid - 1是取不到的,再看判断条件是if(v[mid] > target)这就说明mid也是取不到的,如果right = mid - 1就相当于一次去掉了两个数,这显然是不对的,因为mid - 1在数组中所对应的值有可能是目标值,不能去掉。

代码实现:

#include<bits/stdc++.h>
using namespace std;
int main()

{
    vector<int> v = {-1,0,1,5,6,8,10,82,699};
    int left = 0, right = v.size() - 1;
    int target = 8;
    while(left < right){
        int mid = (left + right) / 2;
        if(v[mid] > target)
            right = mid;
        else if(v[mid] < target)
            left = mid + 1;//left还是加1,因为左区间是能取到的
        else{
            cout << mid;//找到直接输出并return
            return 0;
        }
    }
    cout << -1;//没找到就输出-1
    return 0;
}

 

标签:二分,right,target,int,mid,查找,left
From: https://www.cnblogs.com/linx000/p/17843938.html

相关文章

  • C++U4-第05课-二分查找
    上节课作业部分(点击跳转)  引入分治算法概念  二分法分治思想编程题  二分查找能解决的问题不仅仅是找到一个值 题1: 要在一个有序序列中查找一个数,可以使用二分算法。include<iostream>usingnamespacestd;intBinarySearch(inta[],intl,......
  • EXCEL中逆向查找的十种方法
    逆向查找在Excel中指的是根据某个数值或条件,查找该数值或条件所在的单元格位置。逆向查找可以帮助用户快速定位数据,对于数据分析和处理非常有用。下面将详细介绍在Excel中进行逆向查找的十种方法。一、使用MATCH函数MATCH函数可以在指定范围内查找具体数值或条件,并返回该数值或......
  • 第 372 场周赛(位运算技巧,跳表 + 二分,线段树)
     classSolution:deffindMinimumOperations(self,s1:str,s2:str,s3:str)->int:cnt=0fora,b,cinzip(s1,s2,s3):ifnota==b==c:breakcnt+=1ifcnt==0:......
  • 查找正在被你运行的SQL的SQL_ID
    SQL>SHOWFEEDBACKFEEDBACKONfor6ormorerowsSQL_IDOFFSQL>SETFEEDBACKONSQL_IDSQL>SELECTCOUNT(*)FROMDBA_OBJECTS;COUNT(*)----------926331sat?rsecildi.SQL_ID:7r0kgzntdn7sqSQL>SETFEEDBACKOFFSQL_IDSQL&......
  • linux - grep 查找匹配
    在文件中查找匹配的字符串或者模式1.在单个文件中查找给定的字符串grep"string"filename2.在多个文件中查找指定的字符串grep"this"demo_*3.-i选项忽略大小写敏感进行查找grep-i"string"filename4.使用正则表达式进行匹配查找grep"lines.*empty"demo_file5......
  • 二分查找
    二分查找#include<stdio.h>intmain(void){intarr[]={-2,-1,0,1,2,3};//数组intl=0;intr=sizeof(arr)/sizeof(int)-1;//计算数组的大小,然后-1就是最右侧的下标intm,n;scanf("%d",&n);//输入......
  • 二分查找
    二分查找需要满足的条件:用于查找的内容逻辑上来说是需要有序的找的数量只能是一个,而不是多个查找的区间左闭右闭[left,right]左闭右开[left,right)闭区间:是直线上介于固定两点间的所有点的集合(包括给定的两点),用[a,b]来表示(包含两个端点a和b)开区间:指的是......
  • 图论——二分图 学习笔记
    图论——二分图学习笔记定义二分图,又称二部图,英文名叫Bipartitegraph。定义为,一个图,可以将节点划分为两个集合,而集合内部没有相连的边。如图:性质如果对二分图黑白染色,那么每条边两边对应的一定是一个黑点、一个白点;不存在长度为奇数的环,因为只有偶数条边,才能从一个集合......
  • 区间树上查找所有与给定区间相交的区间-算法复杂度正确性证明
    区间树是在平衡树上维护的数据结构,按照左端点大小排序。详见《算法导论》。算法设计思路红黑树的拓展在红黑树上维护结点属性\(min,max\):\(min\)表示该结点及其所有后代结点中的区间低端的最小值。\(max\)表示该结点及其所有后代结点中的区间高端的最大值。在插入时,对结点......
  • 二分查找
    1、二分查找法只适用于从有序的数列中进行查找(比如数字和字母等),将数列排序后再进行查找2、二分查找法的运行时间为对数时间O(㏒₂n),即查找到需要的目标位置最多只需要㏒₂n步,假设从[0,99]的队列(100个数,即n=100)中寻到目标数30,则需要查找步数为㏒₂100,即最多需要查找7次(......