二分查找 -- 力扣(LeetCode)第704题

题目

https://leetcode.cn/problems/binary-search/description/

给定一个 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) 还是 while(left <= right),到底是right = middle呢,还是要right = middle - 1呢?

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

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

下面我用这两种区间的定义分别讲解两种不同的二分写法。

二分法 第一种写法

第一种写法,我们定义 target 是在一个在左闭右闭的区间里,也就是[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,如图所示:

代码如下:(详细注释)(C++)

// 版本一
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)

二分法第二种写法

如果说定义 target 是在一个在左闭右开的区间里,也就是[left, right) ,那么二分法的边界处理方式则截然不同。

有如下两点:

  • 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,如图所示:(注意和方法一的区别

代码如下:(详细注释)(C++)

// 版本二
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)

总结

二分法是非常重要的基础算法,为什么很多同学对于二分法都是一看就会,一写就废

其实主要就是对区间的定义没有理解清楚,在循环中没有始终坚持根据查找区间的定义来做边界处理。

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

本篇根据两种常见的区间定义,给出了两种二分法的写法,每一个边界为什么这么处理,都根据区间的定义做了详细介绍。

相信看完本篇应该对二分法有更深刻的理解了。

其他语言版本

Java

(版本一)左闭右闭区间

class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }
}

(版本二)左闭右开区间

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

Python

(版本一)左闭右闭区间

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1  # 定义target在左闭右闭的区间里,[left, right]

        while left <= right:
            middle = left + (right - left) // 2
            
            if nums[middle] > target:
                right = middle - 1  # target在左区间,所以[left, middle - 1]
            elif nums[middle] < target:
                left = middle + 1  # target在右区间,所以[middle + 1, right]
            else:
                return middle  # 数组中找到目标值,直接返回下标
        return -1  # 未找到目标值

(版本二)左闭右开区间

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)  # 定义target在左闭右开的区间里,即:[left, right)

        while left < right:  # 因为left == right的时候,在[left, right)是无效的空间,所以使用 <
            middle = left + (right - left) // 2

            if nums[middle] > target:
                right = middle  # target 在左区间,在[left, middle)中
            elif nums[middle] < target:
                left = middle + 1  # target 在右区间,在[middle + 1, right)中
            else:
                return middle  # 数组中找到目标值,直接返回下标
        return -1  # 未找到目标值

C

(版本一)左闭右闭区间

// (版本一) 左闭右闭区间 [left, right]
int search(int* nums, int numsSize, int target){
    int left = 0;
    int right = numsSize-1;
    int middle = 0;
    //若left小于等于right,说明区间中元素不为0
    while(left<=right) {
        //更新查找下标middle的值
        middle = (left+right)/2;
        //此时target可能会在[left,middle-1]区间中
        if(nums[middle] > target) {
            right = middle-1;
        } 
        //此时target可能会在[middle+1,right]区间中
        else if(nums[middle] < target) {
            left = middle+1;
        } 
        //当前下标元素等于target值时,返回middle
        else if(nums[middle] == target){
            return middle;
        }
    }
    //若未找到target元素,返回-1
    return -1;
}

(版本二)左闭右开区间 

// (版本二) 左闭右开区间 [left, right)
int search(int* nums, int numsSize, int target){
    int length = numsSize;
    int left = 0;
    int right = length;	//定义target在左闭右开的区间里,即:[left, right)
    int middle = 0;
    while(left < right){  // left == right时,区间[left, right)属于空集,所以用 < 避免该情况
        int middle = left + (right - left) / 2;
        if(nums[middle] < target){
            //target位于(middle , right) 中为保证集合区间的左闭右开性,可等价为[middle + 1,right)
            left = middle + 1;
        }else if(nums[middle] > target){
            //target位于[left, middle)中
            right = middle ;
        }else{	// nums[middle] == target ,找到目标值target
            return middle;
        }
    }
    //未找到目标值,返回-1
    return -1;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/521332.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【毕业论文】酒店价格采集与可视化查询设计与实现开题报告2000字

酒店价格采集与可视化查询设计与实现开题报告 研究背景 随着互联网技术的飞速发展&#xff0c;人们获取信息的途径越来越多样化。特别是在旅游行业中&#xff0c;消费者对于酒店价格的透明度和实时性要求越来越高。美团、大众点评、抖音等平台作为信息聚合和分享的重要渠道&a…

SpringMVC框架简介

前言 现在由于功能以及业务的复杂性&#xff0c;大部分系统从技术上就拆分开为前后端分离&#xff0c;单体应用我都很少没接触了&#xff0c;导致现在对springMVC那套都忘记了很多东西&#xff0c;因此这篇文章在来回忆一下SpringMVC这个框架&#xff1b;很多时候因为业务的需…

SQL语言

一、DDL数据库定义语言 1、登录mySQL mysql -u"用户名" -p"密码" -h"登录地址 -h&#xff1a;默认为本机 示例&#xff1a; 2、查看当前存在的数据库 show databases; 示例&#xff1a; 3、创建数据库database create…

Jenkins (五) - Docker SonarQube

Jenkins (五) - Docker SonarQube Jenkins 集成 SonarQube&#xff0c;编译项目并通过SonarQube分析项目 前提 基于已有的环境 Jenkins (四) - Docker SonarQube 基于 Jenkins (三) - 拉取编译 上的mockito-demo工程 配置工程 Administration -> Projects -> Manage…

Java数据结构队列

队列(Queue) 概念 队列的使用 注意&#xff1a;Queue是个接口&#xff0c;在实例化时必须实例化LinkedList的对象&#xff0c;因为LinkedList实现了Queue接口。 import java.util.LinkedList; import java.util.Queue;public class Test {public static void main(String[]…

使用GPT需要注意的事项

GPT出来之后&#xff0c;基本就告别浏览器搜索问题答案了。将问题原封不动的copy给GPT基本可以得到解答。 但是这个也有弊端&#xff0c;那就是太依赖GPT了。 1&#xff0c;使用GPT需要更强的专业知识&#xff1a;除了能问对问题&#xff0c;还要具备识别GPT&q…

VPDN(L2TP、PPTP)

1、虚拟专用拨号网络 远程接入VPN&#xff0c;客户端可以是PC机 技术&#xff1a;L2TP、PPTP 术语&#xff1a;LAC&#xff1a;L2TP的访问集中器 --- 提供用户的接入 LNS&#xff1a;L2TP的网络服务器 --- 提供L2TP服务的服务器 2、技术 1&#xff09;PPTP 点对点隧道…

深入理解Java匿名内部类(day21)

在Java编程中&#xff0c;匿名内部类是一种非常有用的特性&#xff0c;它允许我们定义和实例化一个类的子类或实现一个接口&#xff0c;而无需给出子类的名称。这种特性使得代码更加简洁、紧凑&#xff0c;尤其适用于一些只使用一次的临时对象。本文将深入探讨Java匿名内部类的…

租用阿里云的服务器多少钱?30元、61元、99元、165元、199元

租个阿里云的服务器多少钱&#xff1f;很便宜&#xff0c;云服务器2核2G3M固定带宽99元一年、2核4G服务器30元3个月、199元一年&#xff0c;轻量应用服务器2核2G3M配置61元一年、2核4G4M带宽165元一年&#xff0c;可以在阿里云CLUB中心查看 aliyun.club 当前最新的优惠券和活动…

基于Socket简单的TCP网络程序

⭐小白苦学IT的博客主页 ⭐初学者必看&#xff1a;Linux操作系统入门 ⭐代码仓库&#xff1a;Linux代码仓库 ❤关注我一起讨论和学习Linux系统 TCP单例模式的多线程版本的英汉互译服务器 我们先来认识一下与udp服务器实现的不同的接口&#xff1a; TCP服务器端 socket()&…

基于单片机电子密码锁系统设计

**单片机设计介绍&#xff0c;基于单片机电子密码锁系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机电子密码锁系统设计概要主要包括以下几个方面&#xff1a; 一、系统概述 基于单片机电子密码锁系统是一个…

打造你的专属云开发环境:支持任意 IDE,任意云服务 | 开源日报 No.215

loft-sh/devpod Stars: 6.9k License: MPL-2.0 devpod 是一个开源的、仅限客户端的、不受限制的工具&#xff0c;可以与任何集成开发环境&#xff08;IDE&#xff09;一起使用&#xff0c;并允许您在任何云端、Kubernetes 或本地 Docker 上进行开发。 使用 devcontainer.json…

贪心算法|45.跳跃游戏II

力扣题目链接 class Solution { public:int jump(vector<int>& nums) {if (nums.size() 1) return 0;int curDistance 0; // 当前覆盖最远距离下标int ans 0; // 记录走的最大步数int nextDistance 0; // 下一步覆盖最远距离下标for (int i 0;…

qt-C++笔记之QLabel加载图片

qt-C笔记之QLabel加载图片 —— 2024-04-06 夜 code review! 文章目录 qt-C笔记之QLabel加载图片0.文件结构1.方法一&#xff1a;把图片放在项目路径下&#xff0c;在 .pro 文件中使用 DISTFILES添加图片文件1.1.运行1.2.qt_test.pro1.3.main.cpp 2.方法二&#xff1a;不在 .pr…

深入浅出 -- 系统架构之分布式集群的分类

一、单点故障问题 集群&#xff0c;相信诸位对这个概念并不陌生&#xff0c;集群已成为现时代中&#xff0c;保证服务高可用不可或缺的一种手段。 回想起初集中式部署的单体应用&#xff0c;因为只有一个节点&#xff0c;因此当该节点出现任意类型的故障&#xff08;网络、硬件…

go | 上传文件分析 | http协议分析 | 使用openssl 实现 https 协议 server.key、server.pem

是这样的&#xff0c;现在分析抓包数据 test.go package mainimport ("fmt""log""github.com/gin-gonic/gin" )func main() {r : gin.Default()// Upload single filer.MaxMultipartMemory 8 << 20r.POST("/upload", func(c *g…

【单片机】心率传感器,串口发送,MAX30102心率传感器模块

数值还是稳定的&#xff0c;但太贵了&#xff0c;stm32单片机的话&#xff0c;直接用这篇博客&#xff08;https://qq742971636.blog.csdn.net/article/details/137359381&#xff09;的代码&#xff0c;一样稳定。 解析这个模块的数据 char rev_max30102_bufferdata[30]; cha…

Flutter学习12 - SharedPreferences

1、shared_preferences 插件 类似于 Android 中的 SharedPreferences&#xff0c;键值对的形式进行本地存储 1.1、引入插件 在 pubspec.yaml 中引入 dependencies:shared_preferences: ^2.1.0在需要用到的文件中引入 import package:shared_preferences/shared_preference…

安全的通信协议HTTPS被攻击改采用什么防护方案

随着互联网的发展&#xff0c;保护用户在网上交换的敏感信息的安全性变得至关重要。HTTPS&#xff08;Hypertext Transfer Protocol Secure&#xff09;作为一种安全的通信协议&#xff0c;通过加密数据传输&#xff0c;保护用户的隐私和数据安全。然而&#xff0c;尽管HTTPS提…

Ubuntu部署LangChain-Chatchat

个人博客&#xff1a;https://blog.lukeewin.top 更多内容欢迎访问我的博客。 一、环境 OS: Ubuntu 20.04 PyTorch: 2.0.0 Python: 3.8 CUDA: 11.8 GPU: RTX 4090 24GB CPU: 12 vCPU Intel(R) Xeon(R) Platinum 8352V CPU 2.10GHz RAM: 90GB 硬盘: 180GB LLM: Chatglm3-6b E…