当前位置: 首页 > news >正文

[LeetCode][面试算法]逻辑闭环的二分查找代码思路

✌️作者清水寺丞
☀️简介:正在学习算法,unity,数据库,计算机通信网络和python。喜欢部署各种奇奇怪怪的小项目。喜欢就点个关注一起学习吧~⛄️⛄️⛄️⛄️

目录

一、前言

二、二分查找

核心思想简述:

三、代码示范1

注释版:

纯净版代码:

四、代码示范2 (left<=right):


一、前言

        作者在学习二分查找时,常常遇到对于二分查找的思想一学就会,真正写起来却困难重重的问题。每一次在写二分查找的代码时,常常弄不清是while(left<right)还是while(left<=right),也常常弄不清楚是left=mid+1还是left=mid。

        于是写下这篇文章,来理清二分思想的思路,从思路上理解是while(left<right)还是while(left<=right);是left=mid+1还是left=mid。

二、二分查找

核心思想简述:

我们在算法运行过程中,每次更新中保证target的下标一定属于一个范围,然后我们不断缩小这个范围,当这个范围小到没有任何数在其中时,数组中没有这个数。

由于我们每次缩小范围都保证target的下标一定属于这个范围,故若数组中有这个数,在这个可能范围缩小到0的过程中,我们一定会发现target在这个范围的中央。

三、代码写法1

题目来自Leetcode

704. 二分查找

我们将在代码的思路简析与注释中了解如何具体确定target可能出现的下标范围。

代码思路简析:我们在算法运行过程中,每次更新中保证target的下标一定属于[left,right),然后我们不断缩小[left,right)这个范围

当left=right或left<right,则范围[left,right)中不存在任何数,而我们在更新中保证了target一定处于[left,right)这个范围中,当[left,right)中不可能存在数时,target一定不存在于数组中。

注释版:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n=len(nums)
        #我们定义target可能的下标范围为[left,right)
        #在算法中缩小范围时我们也要保证每一次更新后,
        #target可能出现的下标范围仍然为[left,right)
        #我们通过不断地缩小target可能出现的范围来找到target
        #若target可能出现的下标范围已经小到没有数在其中
        #则target不存在数组中

        #一开始,target的下标可能存在范围为[0,n)
        left=0
        right=n
        
        #因为target可能出现的下标范围为[left,right)
        #故当left=right时,target已经不可能出现了
        while(left<right):
            #当前搜索范围的中心下标为int((left+right)/2)
            mid=int((left+right)/2)
            if(nums[mid]>target):
                #如果中心的数大于target,由于升序,target的下标可能范围为[left,mid)
                #故为了保证target属于[left,right),right=mid
                right=mid
            elif(nums[mid]<target):
                #如果中心的数小于target,由于升序,target的下标可能范围为(mid,right)
                #故为了保证target属于[left,right),left=mid+1
                left=mid+1
            else:
                #若中心的数就是target,则返回中心下标
                return mid
        
        #当left<right
        #target可能下标范围[left,right)缩小到其中没有一个数
        return -1

纯净版代码:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n=len(nums)
        left=0
        right=n
        while(left<right):
            mid=int((left+right)/2)
            if(nums[mid]>target):
                right=mid
            elif(nums[mid]<target):
                left=mid+1
            else:
                return mid
        
        return -1

四、代码写法2 (left<=right):

这次我们保证target一定在[left,right]的范围内。

大家可以根据之前的逻辑自行练习。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n=len(nums)
        #target下标在[left,right]
        left=0
        right=n-1
        #因为在[left,right]内,所以left=right时范围内仍然有下标存在
        while(left<=right):
            mid=int((left+right)/2)
            if(nums[mid]<target):
                #target属于(mid,right]
                left=mid+1
            elif(nums[mid]>target):
                #target属于[left,mid)
                right=mid-1
            else:
                return mid
        
        return -1

相关文章:

  • 无卷积步长或池化:用于低分辨率图像和小物体的新 CNN 模块SPD-Conv
  • Mysql数据备份(mysqldump的操作)
  • 面向对象编程技术从0总结——“让你对基础技术有一个新的认识”(国庆五万字总结)
  • Spring Webflux - 01 MVC的困境
  • 自动登录禅道和自动开Bug(JMeter中HTTP Cookie管理器和HTTP请求默认值的用法)
  • 【Day23】力扣:LeetCode算法刷题 [927. 三等分 ] [415. 字符串相加]
  • 芯动科技面试——数字IC/FPGA面试案例总结1
  • [SpringMVC] SSM整合-前后台协议联调
  • DOM操作.操作元素内容
  • 【Java SE】String类
  • 数据可视化看板:基于 Echarts + Python Flask 动态实时大屏
  • 5道真题训练|学会了二叉树的前世今生
  • python专区--时间模块
  • 36、Java 中的 String、StringBuilder、StringBuffer、字符串常量池和 intern 方法
  • 基于正交设计的折射反向学习樽海鞘群算法
  • 分享的文章《人生如棋》
  • Angularjs之国际化
  • HashMap剖析之内部结构
  • Java|序列化异常StreamCorruptedException的解决方法
  • Netty 4.1 源代码学习:线程模型
  • PAT A1050
  • Solarized Scheme
  • Spring Cloud中负载均衡器概览
  • Vue全家桶实现一个Web App
  • 订阅Forge Viewer所有的事件
  • 基于Vue2全家桶的移动端AppDEMO实现
  • 解析带emoji和链接的聊天系统消息
  • 微信公众号开发小记——5.python微信红包
  • 正则学习笔记
  • zabbix3.2监控linux磁盘IO
  • ​​快速排序(四)——挖坑法,前后指针法与非递归
  • # 数论-逆元
  • #define
  • (delphi11最新学习资料) Object Pascal 学习笔记---第8章第2节(共同的基类)
  • (k8s中)docker netty OOM问题记录
  • (Matlab)基于蝙蝠算法实现电力系统经济调度
  • (ZT) 理解系统底层的概念是多么重要(by趋势科技邹飞)
  • (附源码)springboot建达集团公司平台 毕业设计 141538
  • (附源码)springboot掌上博客系统 毕业设计063131
  • (附源码)ssm基于web技术的医务志愿者管理系统 毕业设计 100910
  • (附源码)ssm学生管理系统 毕业设计 141543
  • (经验分享)作为一名普通本科计算机专业学生,我大学四年到底走了多少弯路
  • (一)SpringBoot3---尚硅谷总结
  • (一)UDP基本编程步骤
  • (转)【Hibernate总结系列】使用举例
  • ***检测工具之RKHunter AIDE
  • .bat批处理(五):遍历指定目录下资源文件并更新
  • .NET 4.0网络开发入门之旅-- 我在“网” 中央(下)
  • .NET Compact Framework 3.5 支持 WCF 的子集
  • .net core MVC 通过 Filters 过滤器拦截请求及响应内容
  • .Net Core和.Net Standard直观理解
  • .net MySql
  • .NET高级面试指南专题十一【 设计模式介绍,为什么要用设计模式】
  • .NET建议使用的大小写命名原则
  • .pub是什么文件_Rust 模块和文件 - 「译」