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)


相关推荐

  • 再说注解

    再说注解

    2021年12月16日
  • csv文件格式说明[通俗易懂]

    csv文件格式说明[通俗易懂]csv文件应用很广泛,历史也很悠久。有很多种类型的csv格式,常用的是rfc4180定义的格式。csv文件包含一行或多行记录,每行记录中包含一个或多个字段。记录与记录之间使用换行符分隔,最后一个记

  • eclipse安装教程(2021最新版)超级易懂到吐血

    eclipse安装教程(2021最新版)超级易懂到吐血第一步:下载JDK(下载地址)http://www.oracle.com/technetwork/java/javase/downloads/index.html第二步根据自己电脑的系统,选择相应的版本x64代表64位,x86代表32位。点击相应的JDK进行下载点击之后会出现一个对话框同意之后下载。(记住下载到哪,打开之后一路同意安装即可)记住你把JDK安装到哪里,文件路径不要有中文,不然会无法识别,我安装的时候把JDK装到了F盘第三步:配置环境变量这里解释一下什么是环境.

  • scanf格式控制符的完整格式

    scanf格式控制符的完整格式

  • pycharm 命令行_pycharm叫什么

    pycharm 命令行_pycharm叫什么一、pycharm常用命令1全局查找/替换某个字符串ctrl+shift+r2当前文件查找某个字符串ctrl+f3当前文件替换某个字符串ctrl+r4全局查找指定文件名的文件ctrl+shift+n5全局查找指定类名的类ctrl+n二、pycharm常用操作1获取当前文件对应的项目的树形目录结构所在位置点击左侧项…

  • Kotlin vs Java | Java和Kotlin之间的10个区别

    Kotlin vs Java | Java和Kotlin之间的10个区别Kotlin与JavaJava是一种通用的,面向对象的编程语言。Java程序或应用程序将在JVM(Java虚拟机)中执行。它是一种独立的编程语言,可让您在所有支持Java的平台上运行相同的代码。Kotlin是一种开放源代码,通用,静态类型的编程语言。它结合了面向JVM和Android的面向对象和功能性编程功能。它对开发服务器端应用程序更有用,并且允许用户编写简短而有意义的代…

发表回复

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

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