C++实现二分法的一些细节(常用场景)

二分法是在一个排好序的序列(数组,链表等)中,不断收缩区间来进行目标值查找的一种算法,下面我们就来探究二分法使用的一些细节,以及常用的场景:

寻找一个数;寻找左侧边界;寻找右侧边界。

一、二分法的通用框架

int binarySearch(vector<int>& nums, int target){
    int left=0, right=nums.size();
    while(left < right)
    {
        int mid=(left+right)/2;
        if(nums[mid] == target){
            // 条件一:中间的值与目标值相同
        }
        else if(nums[mid] > target){
            // 条件二:中间的值大于目标值
        }
        else if(nums[mid] < target){
            // 条件三:中间的值小于目标值
        }
    }
    return -1;
}

首先,我们先来分析一下右边界 right 的初始值:

  • right=nums.size() 时,初始化的区间就变成了 \([0, right-1]\),即 \([0,right)\);
  • right=nums.size()-1 时,初始化的区间就变成了 \([0, right]\)。

在第一种情况下,当 nums[mid] > target 时,需要将区间向左收缩,即 right=mid。这个做法的逻辑是:既然 mid 位置处大于 target,而查找区间又是 “左闭右开”,因此当 right=mid 时,新的查找区间变成了 \([0, mid)\),这样才不会漏掉值。同理,当 nums[mid] < target 时,需要将区间向右收缩,即 left = mid+1,因为在 "左闭右开" 的区间下,新的查找区间变成 \([mid+1, right)\) 才不会漏掉值。当目标值不在序列中时,需要将 while 的条件写成 while(left < right) 而不是写成 while(left<=right),这样会引起数组越界。

第二种情况的分析类似,这里只给出结论:

  • nums[mid] > target 时,需要将区间向左收缩,即 right=mid-1
  • nums[mid] < target 时,需要将区间向右收缩,即 left = mid+1
  • 当目标值不在序列中时,需要将 while 的条件写成 while(left<=right)

二、二分法查找目标值

在序列中查找一个数,如果存在则返回数的索引,如果不存在则返回 -1 。为了方便分析,我们就只用第一种情况进行说明:

int binarySearch(vector<int>& nums, int target){
    int left=0, right=nums.size();
    while(left < right)
    {
        int mid=(left+right)/2;
        if(nums[mid] == target){
           return mid;	// 查询到目标值,直接返回目标值的位置
        }
        else if(nums[mid] > target){
            right = mid; // 中间的值大于目标值,向左收缩区间
        }
        else if(nums[mid] < target){
            left = mid+1;// 中间的值小于目标值,向右收缩区间
        }
    }
    return -1;	// 当没有找到,直接返回-1
}

三、二分法查找目标值的左右边界

上述代码只能从序列中查找一个目标值并返回位置,当一个序列中目标值不止一个时,我们需要找到目标值最左边的位置和最右边的位置,这时候二分法需要进行改写:

// 查找目标值的左边界
int binarySearch(vector<int>& nums, int target){
    int left=0, right=nums.size();
    while(left < right)
    {
        int mid=(left+right)/2;
        if(nums[mid] == target){
          right = mid;	// 查询到目标值不进行返回,而是收缩区间继续查找
        }
        else if(nums[mid] > target){
            right = mid; // 中间的值大于目标值,向左收缩区间
        }
        else if(nums[mid] < target){
            left = mid+1;// 中间的值小于目标值,向右收缩区间
        }
    }
    return left;
}

根据上述代码,可以发现如果查找目标值的左边界,在满足 nums[mid] == target 时,需要缩小搜索区间的上界 right,在区间 \([left, mid]\) 中继续搜索,直到搜索完毕 left==right。此时 left=right=左边界

查找右边界的做法与左边界类似:

// 查找目标值的左边界
int binarySearch(vector<int>& nums, int target){
    int left=0, right=nums.size();
    while(left < right)
    {
        int mid=(left+right)/2;
        if(nums[mid] == target){
          left = mid+1;	// 查询到目标值不进行返回,而是收缩区间继续查找
        }
        else if(nums[mid] > target){
            right = mid; // 中间的值大于目标值,向左收缩区间
        }
        else if(nums[mid] < target){
            left = mid+1;// 中间的值小于目标值,向右收缩区间
        }
    }
    return left-1;
}

注意这里的判断条件改成了当 nums[mid] == target 时,left = mid+1。因为搜索的区间为 "左闭右开",所以在寻找左边界时可令 right=mid ,在寻找右边界时必须另 left=mid+1,不然程序会一直停在循环里面而无法跳出循环。

到此这篇关于C++实现二分法详解的文章就介绍到这了,更多相关C++实现二分法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现蓝桥杯竞赛题目---搭积木

    小明对搭积木非常感兴趣.他的积木都是同样大小的正立方体. 在搭积木时,小明选取 m 块积木作为地基,将他们在桌子上一字排开,中间不留空隙,并称其为第0层. 随后,小明可以在上面摆放第1层,第2层,--,最多摆放至第n层.摆放积木必须遵循三条规则 规则1:每块积木必须紧挨着放置在某一块积木的正上方,与其下一层的积木对齐: 规则2:同一层中的积木必须连续摆放,中间不能留有空隙: 规则3:小明不喜欢的位置不能放置积木. 其中,小明不喜欢的位置都被标在了图纸上.图纸共有n行,从下至上的每一行分别对应积木

  • C++ LeeCode题目:比特位计数和买卖股票的最佳时机

    目录 一.比特位计数 一.题目 二.代码 二.买卖股票的最佳时机 一.题目 二.代码 总结 一.比特位计数 一.题目 二.代码 十进制转二进制-百度百科 class Solution { public: vector<int> countBits(int n) { vector<int> num; for(int i=0;i<=n;i++){//遍历[0,n],计算每个值对应二进制1的个数 num.push_back(countOne(i)); } return num; }

  • C++中nullptr 和 NULL 的区别及用法

    1. 为什么会有nullptr的出现 目的:nullptr的出现主要是为了替代NULL. 那么,为什么要替代NULL呢? 在NULL的定义中存在会有2种方式,有的编译器会将NULL定义成0,有的编译器会将NULL定义成((void*)0). 那么,这两种定义方式会对c++有什么区别呢? 在c++中不允许( void* )隐式的转成其他类型,在某些编译器把NULL定义成((void*)0)的情况下,当你定义变量去赋值NULL时候,NULL就会变定义为0. 另外,这种问题也会对c++的重载特性造成混

  • C++有符号和无符号之间的转换问题

    先来看一个程序: #include<iostream> int main() { unsigned a=5; int b=-10; std::cout<<b+b<<std::endl;//正常输出 std::cout<<a+b<<std::endl; return 0; } 打印:-20 4294967291 -20正常打印我们都知道,但当一个有符号和一个无符号之间的数进行相加减会发生什么呢? 是这样的:a+b,首先把负数转换为无符号数,然后在进

  • C++入门笔记之std::vector容器详解

    目录 前言 1. vector的构造函数原型: 2. vector的赋值函数原型: 3. vector的容量和大小函数原型: 4. vector的插入和删除函数原型: 5. vector的存取操作函数原型: 6. vector的呼唤容器函数原型: 总结 前言 vector实质是C++的一个类,与数组很相似,但是vector的优势是可以动态扩展,不需要考虑其内存大小. 定义: 向量(Vector)是一个封装了动态大小数组的顺序容器(Sequence Container).跟任意其它类型容器一样,它

  • C++实现二分法的一些细节(常用场景)

    二分法是在一个排好序的序列(数组,链表等)中,不断收缩区间来进行目标值查找的一种算法,下面我们就来探究二分法使用的一些细节,以及常用的场景: 寻找一个数:寻找左侧边界:寻找右侧边界. 一.二分法的通用框架 int binarySearch(vector<int>& nums, int target){ int left=0, right=nums.size(); while(left < right) { int mid=(left+right)/2; if(nums[mid]

  • 详解async/await 异步应用的常用场景

    前言 async/await 语法用看起来像写同步代码的方式来优雅地处理异步操作,但是我们也要明白一点,异步操作本来带有复杂性,像写同步代码的方式并不能降低本质上的复杂性,所以在处理上我们要更加谨慎, 稍有不慎就可能写出不是预期执行的代码,从而影响执行效率.下面将简单地描述一下一些日常常用场景,加深对 async/await 认识 最普遍的异步操作就是请求,我们也可以用 setTimeOut 来简单模拟异步请求. 场景1. 一个请求接着一个请求 相信这个场景是最常遇到,后一个请求依赖前一个请求,

  • java中Lambda常用场景代码实例

    本文实例为大家分享了java中Lambda常用场景的具体代码,供大家参考,具体内容如下 public class test18 { /** * lambda表达式的常用场景 */ @Test public void test() { List<String> list_one = new ArrayList<>(); list_one.add("NIKE"); list_one.add("Addidas"); /** * 用在匿名内部类里简写

  • Git常用场景使用方法

      1. 本地存在多个commit: [场景]代码和远程仓库一致,本地修改后,存在多次本地commit,直接push最新的提交,push成功,但本地多次commit记录也会记录到远程仓库中 [举例]第一次提交:添加File1文件,文件内容666666               第二次提交: 添加File2文件,文件内容888888,修改File1内容 2. 远程仓库代码回退: 先本地版本回退:git reset commitid     本地回退版本强推远程仓库:git push -f 3.

  • Git常用场景使用之分支操作

        1. 拉取推送分支: ​    git branch 分支名 : 创建分支 ​    git checkout 分支名 : 切换分支 ​    git checkout –b 分支名 : 创建并切换到新分支 ​    本地拉取分支后推送到远程: ​        git push <远程主机名> <本地分支名>:<远程分支名>         [注意]直接git push 会将当前本地分支推送到对应远端同名分支,如果远端没有同名分支则会新建同名分支     ​ 

  • React Hooks常用场景的使用(小结)

    前言 React 在 v16.8 的版本中推出了 React Hooks 新特性.在我看来,使用 React Hooks 相比于从前的类组件有以下几点好处: 代码可读性更强,原本同一块功能的代码逻辑被拆分在了不同的生命周期函数中,容易使开发者不利于维护和迭代,通过 React Hooks 可以将功能代码聚合,方便阅读维护: 组件树层级变浅,在原本的代码中,我们经常使用 HOC/render props 等方式来复用组件的状态,增强功能等,无疑增加了组件树层数及渲染,而在 React Hooks

  • JavaScript中Reduce10个常用场景技巧

    目录 累加/累积 求最大/最小值 格式化搜索参数 反序列化搜索参数 拉平嵌套数组 实现 flat 数组去重 数组计数 获取对象多个属性 反转字符串 不知道大家平常用 Reduce 多不多,反正本瓜用的不多.但实际上,Reduce 能做的,比我们能想到的要多得多,本篇带来 10 个Reduce 常用场景和技巧,一定有你不知道~ 冲ヾ(◍°∇°◍)ノ゙ 累加/累积 累加我们可能是最熟悉 Reduce 的一种用法,除此之外,还可以用做累积. // adder const sum = (...nums)

  • Python Decorator装饰器的创建方法及常用场景分析

    目录 前言 一.创建方式 二.常用场景 前言 1.装饰器本质是一个语法糖,是对被装饰方法或类进行的功能扩充,是一种面向切面的实现方法2.装饰器可以分成方法装饰器和类装饰器,他们的区别是一个是用函数实现的装饰器,一个是用类实现的装饰器,他们也都能在方法和类上进行装饰3.类装饰器看起来结构更加清晰,因此下面的代码实现的装饰器全是类装饰器 一.创建方式 1.创建“装饰方法”的类装饰器 from functools import wraps # 装饰器类 class MyDecorator(object

  • mybatis动态sql常用场景总结

    目录 前言 1.if 2. choose.when.otherwise 3. trim.where.set 4. foreach 前言 平时在开发中,针对动态sql这块目前是薄弱点,自己根据官网在对应项目边测试边写博客,此篇只是为了加深动态sql的熟练度,有不到之处敬请批评指正! 1.if 使用动态 SQL 最常见情景是根据条件包含 where 子句的一部分.比如: <select id="findActiveBlogWithTitleLike" resultType="

  • Java8 forEach常用场景代码实例

    forEach and Map 1.1 通常这样遍历一个Map Map<String, Integer> items = new HashMap<>(); items.put("A", 10); items.put("B", 20); items.put("C", 30); items.put("D", 40); items.put("E", 50); items.put("

随机推荐