二分查找的两种形式(C++实现)

这篇具有很好参考价值的文章主要介绍了二分查找的两种形式(C++实现)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

现在有一个这样的问题需要求解

题目要求:给定一个n个元素的(升序)整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在返回下标,否则返回-1

示例

输入: nums= [-1,0,3,5,9,12]
target= 9
输出: 4
解释: 9 出现在 nums中并且下标为 4
输入: nums= [-1,0,3,5,9,12], target= 2
输出: -1
解释: 2 不存在 nums中因此返回 -1

继上次写完二分查找后,又在网上查看了其他资料,发现二分查找其实常用的有两种写法,这篇文章里(二分查找)只写了一种形式,而且可能介绍的不是很详细,所以这里将二分查找的两种形式做以归纳总结,方便记忆。

二分查找的两种形式的主要区别在于区间的定义,①左闭右闭[left,right],②左闭右开[left,right)

具体来说就是下面这两种表示区间的方式,虽然表现方式略有差异,但实际上表达的区间范围是一致的,殊途同归(相信大家对初中数学开闭区间的描述仍有印象) 

二分查找的两种形式(C++实现) 

由于区间定义的微小差别,导致程序中mid变量的取值也有相应的改变(一定得改变,不然就会出错),下面我们来介绍一下这两种形式

①左闭右闭[left,right]

我们定义target是在一个左闭右闭[left,right]的区间里,那么要注意两个事情

  • while的循环条件;while(left<=right)。在while的循环条件里面就要用<= ,因为这个时候left==right是有意义的
  • if(nums[mid]>target)之后对right怎样处理?right要赋值为mid-1,因为当前这个nums[mid]一定不是target,那么接下来要查找的左区间的右边界就是mid-1

具体怎么写呢?

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right)
        {
            int mid=(right-left)/2+left;
            if(nums[mid]==target)
            {
                return mid;
            }
            else if(nums[mid]>target)
            {
                right=mid-1;
            }
            else
            {
                left=mid+1;
            }
        }
        return -1;
    }
};

对上面的程序做简单注释

int left=0,right=nums.size()-1;

定义一个区间,左边界left=0,右边界right=nums.size()-1,实际上就是说定义了一个闭区间,要求包括整个数组的所有元素。定义target在这个区间范围里。

注意代码right=nums.size()-1,为什么要减1?因为nums.size()返回的是nums中有多少个元素,而我们又知道数组的下标是从0开始的,所以一个数组的最后一个元素的下标一定是这个数组中拥有元素的个数减1

二分查找的两种形式(C++实现)

while(left<=right)

这里为什么要写成<=号,我们之前也说过,因为当left==right时,仍然是有意义的。

int mid=(right-left)/2+left;

这里为什么要把mid写成这样?其实它和

int mid = (left+rirht)/2

是一样的,那为什么要那样写而不写成下面这样,主要原因是怕内存溢出,

int类型的整数能够表示的最大数字是2147483647 ,假如在运行过程中,left不断逼近right,直到left和right两个数都接近2147483647,他们两个再相加结果就会溢出,会变成负数,所以改用mid=(right-left)/2+left

二分查找的两种形式(C++实现)

通过上面这个小测试我们就可以想通为什么要写成 mid=(right-left)/2+left的样子了。

在这里可能大家还会碰到另外一种书写形式

int mid=((right-left)>>1)+left

这里的“>>"运算符是右移运算符,

举个例子

二分查找的两种形式(C++实现) 

二分查找的两种形式(C++实现)二分查找的两种形式(C++实现)  

 所以我们可以知道 int mid=((right-left)>>1)+left 和 int mid=(right-left)/2+left; 这两种形式是等效的,但是位运算符>>比’ / ‘快一些。因为位运算符直接对内存数据进行操作,不需要转成十进制,因此处理速度快;

if(nums[mid]==target)
{
    return mid;
}

这句代码应该很好理解,当nums[mid]==target,就是说如果mid位置处的值恰好等于我们要找的target,那直接返回mid就可以了,后面的缩小区间再查找就不用执行了,因为数组是升序的而且元素不重复,说明只有一个位置处的值等于target

 else if(nums[mid]>target)
     {
         right=mid-1;
     }

这句就是说target在原区间的左半边,所以新区间的范围是[left,mid-1]

else
    {
         left=mid+1;
    }

 这句就是说target在原区间的右半边,所以新区间的范围是[mid+1,right]

while循环之外就是说 在数组中没有找到target,就返回-1; 

②左闭右开[left,right)

如果定义target在左闭右开的区间里,[left,right),那么边界处理问题就会发生变化,要注意这一点,否则就会出错

  • while(left<rigth),注意这里使用的是<,因为left==right在区间[left,right)是没有意义的
  • if(nums[mid]>target),right=mid,因为当前nums[mid]不等于target,去左区间继续寻找,但是这时候由于区间是左闭右开的,所以right更新为mid,

核心代码如下

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right)
    {
        int mid = (right - left) / 2 + left;
        if (nums[mid] == target)
        {
            return mid;
        }
        else if (nums[mid] > target)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    return -1;

}

这里就不给大家逐句讲解了,唯一需要注意的就是

else if (nums[mid] > target)
  {
      right = mid;
  }

这里涉及到右区间的处理问题,大家注意一下。 

接下来我们把两种形式的代码放在vs里面测试一下

#include<iostream>
#include<vector>
using namespace std;

①[left,right]
//int search(vector<int>& nums, int target) {
//    int left = 0, right = nums.size() - 1;
//        while (left <= right)
//        {
//            int mid = (right - left) / 2 + left;
//            if (nums[mid] == target)
//            {
//                return mid;
//            }
//            else if (nums[mid] > target)
//            {
//                right = mid - 1;
//            }
//            else
//            {
//                left = mid + 1;
//            }
//        }
//        return -1;
// }

//②[left,right)
int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right)
    {
        int mid = (right - left) / 2 + left;
        if (nums[mid] == target)
        {
            return mid;
        }
        else if (nums[mid] > target)
        {
            right = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
    return -1;

}

int main()
{
    vector<int> vec{ 1,4,5,7,11,14,18 };
    cout << "vec: ";
    for (auto c : vec)
    {
        cout << c << " ";
    }
    cout << endl;
    int tar = 5;
   /* int tar = 2;*/
    int i=search(vec, tar);
    if (i >= 0)
        cout << tar<<" index is " << i << endl;
    else
        cout << tar<<" not found" << endl;
}

程序运行结果如下, 

二分查找的两种形式(C++实现) 

二分查找的两种形式(C++实现)文章来源地址https://www.toymoban.com/news/detail-437303.html

到了这里,关于二分查找的两种形式(C++实现)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 问题 C: 二分查找右侧边界(C++)(二分查找)

    1.题目描述 2.AC 问题 C: 二分查找右侧边界 时间限制: 1.000 Sec  内存限制: 128 MB 提交 状态 题目描述 请在一个有序不递减的数组中(数组中的值有相等的值),采用二分查找,找到最后1次出现值x的位置,如果不存在x请输出-1。 请注意:本题要求出q个x,每个x在数组中第一

    2024年02月03日
    浏览(45)
  • C++二分算法(二分查找&二分答案)细节详解

     二分算法可以分为 二分查找 和 二分答案 。 以在一个 升序数组 中查找一个数为例。它每次考察数组当前部分的 中间元素 ,如果中间元素刚好是要找的,就结束搜索过程;如果中间元素小于所查找的值,那么左侧的只会更小,不会有所查找的元素,只需到右侧查找;如果

    2024年02月08日
    浏览(53)
  • 二分查找:34. 在排序数组中查找元素的第一个和最后一个位置

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》《C++》《算法》 本篇文章仅是作为小白的我的一些理解,,如果有错误的地方,希望大佬们指出。 题目链接: 34. 在排序数组中查找元素的第一个和最后一个位置 本题数组元素不唯一,可能存在多个target,我们就是

    2024年02月08日
    浏览(48)
  • 34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)

    二分查找到目标值然后左右找到坐标 问题在于:找左右坐标的时候时间复杂度不是 O(logN) 之前提到过二分查找不仅可找到相等的数值,更关键的是 它可以将数组分为截然不同的两种情况 ,因此我们可以借助这个性质找到 第一个大于等于 target 的值(左下标) 和 第一个大于

    2024年01月22日
    浏览(53)
  • 二分查找实例1(在排序数组中查找元素的第一个和最后一个位置)

    给你一个按照非递减顺序排列的整数数组  nums ,和一个目标值  target 。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值  target ,返回  [-1, -1] 。 你必须设计并实现时间复杂度为  O(log n)  的算法解决此问题。 示例 1: 示例 2: 示例 3: 提示

    2024年02月09日
    浏览(46)
  • 一个几乎全民都会的算法——二分查找

    20年前央视2套有一档叫《幸运52》的综艺节目,其中一个环节叫《幸运超市》,每一期已故著名主持人咏哥都会给佳宾们出示几个商品,凡是佳宾猜中价格的,就能获赠这件商品。这档节目红极一时,被很多地方卫视节目复制抄袭。 比如,上面这段视频(gif图)的配音这样的:

    2023年04月09日
    浏览(42)
  • 【数据结构】稀疏矩阵存储的三种方法及三元组表示稀疏矩阵转置算法的两种实现 —— C++

    1. 三元组顺序表数据结构 注意:data[]中的元素是按行存储或者按列存储的,所以 在将三元组逆置时,不能简单地将行列下标对换,data[]数组中元素的顺序也需要重新排列 2. 三元组表示稀疏矩阵转置算法1 3. 三元组表示稀疏矩阵转置算法2:快速转置 为了 便于随机存取任意一

    2024年02月05日
    浏览(45)
  • C++二分查找算法:132 模式枚举3

    本篇是视频课程的讲义,可以看直接查看视频。也可以下载源码,包括空源码。 二分查找算法合集 包括题目及代码 C++二分查找算法:132 模式解法一枚举3 C++二分查找算法:132 模式解法二枚举2 代码最简洁 C++二分查找算法:132 模式解法三枚举1 性能最佳 C++单调向量算法:1

    2024年02月04日
    浏览(41)
  • 【动态规划】【二分查找】C++算法 466 统计重复个数

    视频算法专题 动态规划汇总 二分查找 定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。 例如,str == [“abc”, 3] ==“abcabcabc” 。 如果可以从 s2 中删除某些字符使其变为 s1,则称字符串 s1 可以从字符串 s2 获得。 例如,根据定义,s1 = “abc” 可以从 s2 = “abdbec” 获得,仅需

    2024年01月23日
    浏览(50)
  • C++二分查找算法:132 模式解法二枚举2

    二分查找算法合集 包括题目及代码 C++二分查找算法:132 模式解法一枚举3 C++二分查找算法:132 模式解法二枚举2 代码简洁 C++二分查找算法:132 模式解法三枚举1 性能最佳 C++单调向量算法:132 模式解法三枚举1 代码更简洁 C++二分查找算法:132模式枚举3简洁版 代码简洁,性能

    2024年02月05日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包