c++二分法查找_二分法查找python代码

c++二分法查找_二分法查找python代码二分法:二分法应用条件:1)数组为有序数组。2)同时题目还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的。区间的定义:区间的定义不同代码就不同。1)定义target在[left,right]区间while(left<=right)要使用<=,因为left==right是有意义的,所以使用<=。if(nums[middle]>target)right要赋值为middle-1,因为当前这个nums[mid

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

二分法:

二分法应用条件:1)数组为有序数组。2)同时题目还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的。

区间的定义:

区间的定义不同代码就不同。
1)定义target在[left, right]区间
while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=。if (nums[middle] > target) right 要赋值为 middle – 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle – 1。
以leecode704为例:

// 定义target在[left, right]区间
class Solution { 
   
public:
    int search(vector<int>& nums, int target) { 
   
        int left = 0;
        int right = nums.size() - 1; // 定义target在左闭右闭的区间里,[left, right]
        while (left <= right) { 
    // 当left==right,区间[left, right]依然有效,所以用 <=
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) { 
   
                right = middle - 1; // target 在左区间,所以[left, middle - 1]
            } else if (nums[middle] < target) { 
   
                left = middle + 1; // target 在右区间,所以[middle + 1, right]
            } else { 
    // nums[middle] == target
                return middle; // 数组中找到目标值,直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

Jetbrains全家桶1年46,售后保障稳定

2)如果说定义 target 是在一个在左闭右开的区间里[left, right) :

// 定义target在[left, right)区间
// 版本二
class Solution { 
   
public:
    int search(vector<int>& nums, int target) { 
   
        int left = 0;
        int right = nums.size(); // 定义target在左闭右开的区间里,即:[left, right)
        while (left < right) { 
    // 因为left == right的时候,在[left, right)是无效的空间,所以使用 <
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) { 
   
                right = middle; // target 在左区间,在[left, middle)中
            } else if (nums[middle] < target) { 
   
                left = middle + 1; // target 在右区间,在[middle + 1, right)中
            } else { 
    // nums[middle] == target
                return middle; // 数组中找到目标值,直接返回下标
            }
        }
        // 未找到目标值
        return -1;
    }
};

参考:
代码随想录:https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%BB%E7%BB%93

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/230801.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • nginx基本配置「建议收藏」

    nginx基本配置「建议收藏」Nginx概念Nginx是一个高性能的HTTP和反向代理服务。其特点是占有内存少,并发能力强,事实上nginx的并发能力在同类型的网页服务器中表现较好。Nginx专为性能优化而开发,性能是

  • 【愚公系列】2022年02月 wireshark系列-数据抓包分析之DHCP协议

    【愚公系列】2022年02月 wireshark系列-数据抓包分析之DHCP协议实验步骤一获取DHCP数据包在windows平台上获取DHCP数据包在windows平台上,可以使用两种简单的方法实现,其原理一样。(1)在cmd上,使用ipconfig命令来获取。执行完上述命令后,将释放当前使用的地址信息。重新获取地址信息,执行命令如下执行完上面的命令后,将重新获取地址信息。在获取地址时,将会经过上面讲述的DHCP的4个阶段。这样,我们就能获取到DHCP数据包了。(2)通过禁用和启用网卡获取DHCP数据包在windows平台上,也可以通过禁用和启用网卡获取DHCP数

  • sensor接口之DVP

    sensor接口之DVPsensor接口之DVP什么是DVPDVP时序PCLK、HSYNC、VSYNC对应关系sensor并行输出说明实际测量DVP信号什么是DVPDVP(DigitalVideoPort)是传统的sensor输出接口,采用并行输出方式,d数据位宽有8bit、10bit、12bit、16bit,是CMOS电平信号(重点是非差分信号),PCLK最大速率为96MHz,接口如下图:PCLK:pix…

  • Java菜鸟教程 递归算法与Scanner类「建议收藏」

    Java菜鸟教程 递归算法与Scanner类「建议收藏」最近笔者学习了递归算法与Scanner类的简单应用,在此做一些分享。递归算法:Recursion是一种解决问题的方法,就是把问题逐渐简单化。遵循“自己调用自己”的基本思想。运用递归算法解决问题的时候,要注意定义递归头,即什么时候不调用自身的方法;以及定义递归体:什么时候要调用自身的方法。可以用ifelse语句来控制,形成一个循环。以下是几个例子。staticinta=0;pu

  • PHP 常用的header头部定义汇总

    PHP 常用的header头部定义汇总

  • latex中的括号怎么打_小括号和中括号的简便算法

    latex中的括号怎么打_小括号和中括号的简便算法https://blog.csdn.net/han____shuai/article/details/49679335功能语法显示不好看    (\frac{1}{2})好一点\left(\frac{1}{2}\right)您可以使用\left和\right来显示不同的括号:功能语法显示圆括号,小括号\left( \frac{a}{b}\right)方括号,中括号\left[ \frac…

    2022年10月11日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号