C++怎么实现二分法

发布时间:2022-03-28 10:05:07 作者:iii
来源:亿速云 阅读:132

本篇内容介绍了“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 的初始值:

在第一种情况下,当 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),这样会引起数组越界。

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

二、二分法查找目标值

在序列中查找一个数,如果存在则返回数的索引,如果不存在则返回 -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++怎么实现二分法”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!

推荐阅读:
  1. java的二分法查找是什么?怎么实现?
  2. java 二分法详解几种实现方法

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c++

上一篇:C++ LeeCode二叉树的中序遍历是什么

下一篇:C++中nullptr和NULL怎么用

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》