首页 > 编程语言 >算法 -- 二分查找

算法 -- 二分查找

时间:2023-08-25 13:11:07浏览次数:61  
标签:二分 right target nums -- middle 查找 区间 left

力扣题目链接

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

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

示例 2:

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

提示:

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

思路

这道题目的前提是数组为有序数组,且强调数组中无重复元素,因为一旦有重复元素,则二分法将有可能查到多个下标。

二分法很容易写乱,主要是因为对区间的定义没有想清楚,区间的定义就是不变量。要在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。

写二分法,区间的定义一般为两种,左闭右闭即[left, right],或者左闭右开即[left, right)。

左闭右闭

此写法,将target定义在一个闭合的区间内,即[left, right],这一步很重要。
因为左右皆闭合:

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

例如在数组:1,2,3,4,7,9,10中查找元素2,如图所示:

左闭右闭

实现代码 -- Java:

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;
    }
};
  • 时间复杂度:O(log n)
  • 空间复杂度:O(1)

左闭右开

对于左闭右开的情况,处理方式稍有不同:

  • while (left < right),这里使用 < ,因为left == right在区间[left, right)是没有意义的
  • if (nums[middle] > target) right 更新为 middle,因为当前nums[middle]不等于target,去左区间继续寻找,而寻找区间是左闭右开区间,所以right更新为middle,即:下一个查询区间不会去比较nums[middle]

在数组:1,2,3,4,7,9,10中查找元素2
左闭右开

实现代码 -- Java:

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;
    }
};
  • 时间复杂度:O(log n)
  • 空间复杂度:O(1)

总结

二分法算是比较基础的算法,他的重点在于对判断区间的分析,在循环中没有始终坚持根据查找区间的定义来做边界处理。

区间的定义就是不变量,那么在循环中坚持根据查找区间的定义来做边界处理,就是循环不变量规则。

参考链接:
代码随想录--二分查找

标签:二分,right,target,nums,--,middle,查找,区间,left
From: https://www.cnblogs.com/chenzhang0419/p/17656659.html

相关文章

  • Spring加载机制的设计与实现
    骑士李四记录:1.ApplicationContext是什么ApplicationContext是Spring上下文的核心接口,描述了Spring容器的所有基本功能,是SpringContext(Spring上下文)模块的核心设计。想了解Spring的加载机制,则必须先明白SpringApplicationContext(后简称Spring上下文)到底是什么、是怎么设计的、......
  • 过滤器| 拦截器| 监听器的区别与使用
    骑士李四记录:1.过滤器(Filter):过滤器依赖于servlet容器。在实现上基于函数回调。几乎可以对所有请求进行过滤。缺点是一个过滤器实例只能在容器初始化时调用一次。2.拦截器(Interceptor)拦截器依赖于web框架,在SpringMVC中依赖于SpringMVC框架。实现上基于java反射机制,属于面向切......
  • curl的用法| curl是什么意思
    骑士李四记录;1.在服务器上查看请求是否返回正常:curl-ihttp://127.0.0.1:8080/api/abc返回这个表示请求返回ok。更多参考大神笔记:http://www.ruanyifeng.com/blog/2019/09/curl-reference.html......
  • java.lang.NoClassDefFoundError问题解决方案
    骑士李四记录:场景在pom.xml中引入一个包,之后启动部署项目,出现java.lang.NoClassDefFoundError的问题。报错信息:解决方案:加入这段代码<plugin><groupId>org.apache.maven.plugins</groupId><artifactId>maven-dependency-plugin</artifactId><executi......
  • The POM for xxxx is missing, no dependency information available解决方案
    骑士李四记录:maveninstall报错ThePOMforcom.xxxxismissing…nodependencyinformationavailable解决方案:现在父工程上先执行maveninstall,这时候会自动下载很多依赖包,等到父工程buildsuccess的时候,在执行子工程。......
  • Linux命令之文件的增、删、移、查、授权操作
    骑士李四记录:Linux常用命令文件基本属性chgrp:更改文件属性:chgrp[-R]属组名文件名-R:递归更改文件属组,就是在更改某个目录文件的属组时,如果加上-R的参数,那么该目录下的所有文件的属组都会更改。chown:更改文件属主,也可以同时更改文件属组chmod:更改文件9个属性对文件操作:4.下载文......
  • Docker下spark环境搭建
    RUNecho"InstallSpark"&&\wget-O/tmp/spark-2.3.4-bin-hadoop2.6.tgzhttp://mirror.bit.edu.cn/apache/spark/spark-2.3.4/spark-2.3.4-bin-hadoop2.6.tgz&&\cd/tmp/&&\tar-zxvf/tmp/spark-2.3.4-bin-hado......
  • Spring框架源码结构
    骑士李四记录:Spring源码解析Spring是一款用于简化企业级Java应用开发的分层开源框架,它有着强大的扩展、融合能力,善于将各种单层框架完美地糅合在一起,并建立一个完整体系,统一、高效地构造可提供企业级服务的应用系统。Spring主要分为8大模块:数据处理模块(DataAccess/Integration)、......
  • 高并发web开发框架解决方案
    对于大型网站来说,所采用的技术涉及面极其广泛,从硬件到软件、编程语言、数据库、Web服务器、防火墙等各个领域都有了很高的要求,提高系统高并发性能方案措施:减少数据库访问次数,文件和数据库分离,大数据分布式存储,服务器的集群负载均衡,页面缓存的使用,nosql内存数据库代替关系型数据库......
  • git总是提示要填账号密码| fatal: Authentication failed for 'http://gitlab.xxx.git
    骑士李四记录:gitclone/gitpull等git操作总是提示要填账号密码问题?执行这段命令:gitconfig--globalcredential.helperstore这个命令则是在你的本地生成一个账号密码的本子记录信息,这样就不用每次都输入了,第一次还是需要输入。......