对二分搜索的理解 Go语言版

二分搜索大家都很熟悉,首先我们先来看看基本框架

func binarySearch(nums []int, target int) int {left, right := 0, ...for ... {mid := left + (right-left)/2if nums[mid] == target {...} else if nums[mid] < target {left = ...} else if nums[mid] > target {right = ...}}return ...
}

看完代码之后我们会发现:

  1. 数组得是有序的才能成立
  2. 在存在两个及以上的答案时,只能找出一个,至于下标的情况我觉得可以自定义
  3. 如果数组长度为偶数,初始化时mid在中间偏左的那一格

接下来在实战中看:

寻找一个数

这可以说是最简单的内容

func binarySearch(nums []int, target int) int {left := 0 //right := len(nums) - 1 for left <= right {mid := left + (right - left) / 2 if nums[mid] == target { return mid} else if nums[mid] < target { left = mid + 1 // [mid + 1, right]} else if nums[mid] > target { // 目标值在左半部分,注意right = mid - 1 // [left, mid - 1]}}return -1 // 未找到
}

这里需要注意一点,为何是 for left <= right 而不是 for left < right

我们可以先从最极端的情况入手,假设要寻找的数在最后一个,那么在前一步应该是 left = right - 1, mid = left ,然后 left = mid + 1 = right,在进行循环时,循环就会进不去。

从理论上解释,因为在之前设定值时,数组为闭区间 [left, right] ,所以得保证边界值,也就是说,循环的条件设定和搜索区间设定是相关联的

寻找左侧边界

那么接下来看一下右侧开区间的做法:

func leftBound(nums []int, target int) int {left := 0right := len(nums)for left < right {mid := left + (right - left) / 2if nums[mid] == target {right = mid} else if nums[mid] < target {left = mid + 1 // [mid + 1, right)} else if nums[mid] > target {right = mid // [left, mid)}}return left
}

不难发现,随着区间的修改,在对应条件下的操作也会对应转换。

在这里阐述一点我的个人想法,二分查找的最大特点在于区间设定,而在对应条件下做出的操作有点像递归,基本盘并没有改变

寻找右侧边界

func right_bound(nums []int, target int) int {left, right := 0, len(nums)for left < right {mid := left + (right-left)/2if nums[mid] == target {   left = mid + 1        } else if nums[mid] < target {left = mid + 1} else if nums[mid] > target {right = mid}}return left - 1  
}

这里面的精华在于

if nums[mid] == target {   left = mid + 1 

他并没有直接的收网,而是继续直到最右侧的诞生,这也得益于mid的设置,可以把他看成以left为基准向前进

实战

我们来看力扣的34. 在排序数组中查找元素的第一个和最后一个位置

直接把方法摆上既可以解决

func searchRange(nums []int, target int) []int {left := leftBound(nums, target)right := rightBound(nums, target)return []int{left, right}
}func leftBound(nums []int, target int) int {left, right := 0, len(nums)-1for left <= right {mid := left + (right - left) / 2if nums[mid] < target {left = mid + 1} else if nums[mid] > target {right = mid - 1} else if nums[mid] == target {// 别返回,锁定左侧边界right = mid - 1}}// 判断 target 是否存在于 nums 中if left < 0 || left >= len(nums) {return -1}// 判断一下 nums[left] 是不是 targetif nums[left] == target {return left}return -1
}func rightBound(nums []int, target int) int {left, right := 0, len(nums)-1for left <= right {mid := left + (right - left) / 2if nums[mid] < target {left = mid + 1} else if nums[mid] > target {right = mid - 1} else if nums[mid] == target {// 别返回,锁定右侧边界left = mid + 1}}// 判断 target 是否存在于 nums 中// if left - 1 < 0 || left - 1 >= len(nums) {//     return -1// }if right < 0 || right >= len(nums) {return -1}if nums[right] == target {return right}return -1
}

当然也有另外一种解法,力扣显示这种时间复杂度更低
在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

redis非关系型数据库(缓存型数据库)——中间件

【重点】redis为什么这么快&#xff1f;&#xff08;应届&#xff09; ①redis是纯内存结构&#xff0c;避免磁盘I/O的耗时 ②redis核心模块是一个单进程&#xff0c;减少线程切换和回收线程资源时间 ③redis采用的是I/O的多路复用机制&#xff08;每一个执行线路可以同时完…

ESP32-Web-Server编程- JS 基础 3

ESP32-Web-Server编程- JS 基础 3 概述 本示例演示通过 button 控件的 onclick 内联属性&#xff0c;实现在网页上点击按钮&#xff0c;切换 LED 灯图标的转变。 示例解析 前端设计 前端代码建立了一个 id 为 “imageLamp” 的图片对象。并建立两个按钮&#xff0c;设计两…

Python逻辑运算符及其用法

逻辑运算符用于操作 bool 类型的变量、常量或表达式&#xff0c;逻辑运算的返回值也是 bool 值。 Python 的逻辑运算符有如下三个&#xff1a; and&#xff1a;与&#xff0c;前后两个操作数必须都是 True 才返回 True&#xff1b;否则返回 False。 or&#xff1a;或&#x…

SpringBoot 2 系列停止维护,Java8 党何去何从?

SpringBoot 2.x 版本正式停止更新维护&#xff0c;官方将不再提供对 JDK8 版本的支持 SpringBoot Logo 版本的新特性 3.2 版本正式发布&#xff0c;亮点包括&#xff1a; 支持 JDK17、JDK21 版本 对虚拟线程的完整支持 JVM Checkpoint Restore&#xff08;Project CRaC&…

0005Java程序设计-ssm基于微信小程序的校园求职系统

文章目录 摘 要目 录系统设计开发环境 编程技术交流、源码分享、模板分享、网课分享 企鹅&#x1f427;裙&#xff1a;776871563 摘 要 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据…

工艺系统所管理数字化实践

摘要 本文介绍了上海核工程设计研究院在数字化转型方面的实践&#xff0c;包括业务数字化和管理数字化两个方面。业务数字化方面&#xff0c;该院通过开发小工具改进工作流程。管理数字化方面&#xff0c;该院采用零代码平台集中管理管道力学信息相关模型和数据&#xff0c;并…

visionOS空间计算实战开发教程Day 2 使用RealityKit显示3D素材

我们在​​Day1​​中学习了如何创建一个visionOS应用&#xff0c;但在第一个Demo应用中我们的界面内容还是2D的&#xff0c;看起来和其它应用并没有什么区别。接下来我们先学习如何展示3D素材&#xff0c;苹果为方便开发人员&#xff0c;推出了RealityKit&#xff0c;接下来看…

【活动回顾】sCrypt在2023伦敦区块链大会上的精彩表现

2023伦敦区块链大会&#xff0c;是本年度最盛大的比特币及区块链行业活动。大会于2023年5月31日至6月2日&#xff0c;在伦敦女王伊丽莎白二世中心举行&#xff0c;旨在展示BSV区块链的真正潜力。 sCrypt Inc 的创始人兼 CEO 刘晓晖&#xff0c; 作为演讲嘉宾出席了会议。他向大…

前端开发_HTML

简介 CSS用于美化内容 HTML用于摆放内容 可以理解为HTML是基础&#xff0c;CSS是工具 HTML定义 HTML 超文本标记语言——HyperText Markup Language 超文本——链接 标记——标签&#xff0c;即带尖括号的文本 标签语法 双标签 开始标签&#xff1a; <xxx> 即尖…

vue el-table表格中每行上传文件(上传简历)操作

1、HTML中 <el-table :data"formInfo.userListDto" border stripe max-height"400"><el-table-column type"index" label"序号" width"50"> </el-table-column><el-table-column prop"realName&q…

鸿蒙4.0开发笔记之ArkTS装饰器语法基础@Extend扩展组件样式与stateStyles多态样式(十一)

一、Extend扩展组件样式 1、作用 前文提到可以使用Styles用于样式的扩展&#xff0c;在Styles的基础上&#xff0c;ArkTS语法还提供了Extend&#xff0c;⽤于扩展原生组件样式&#xff0c;包括Text、Button等等。 2、定义语法 Extend(UIComponentName) function functionNam…

在PyCharm中配置PyQt5环境

在PyCharm中配置PyQt5环境 文章目录 1.安装第三方库2.PyQt5设计器3.PyUIC转换工具 &#x1f339;꧔ꦿ&#x1f339;꧔ꦿ&#x1f339;꧔ꦿ&#x1f339;꧔ꦿ&#x1f339;꧔ꦿ&#x1f339;꧔ꦿ&#x1f339;꧔ꦿ&#x1f339;꧔ꦿ&#x1f339;꧔ꦿ&#x1f339;꧔ꦿ&#x1…

【AI认证笔记】NO.2人工智能的发展

目录 一、人工智能的发展里程碑 二、当前人工智能的发展特点 1.人工智能进入高速发展阶段 2.人工智能元年 三、人工智能高速发展的三大引擎 1.算法突破 2.算力飞跃 3.数据井喷 四、AI的机遇 五、AI人才的缺口 六、行业AI 人工智能算法&#xff0c;万物互联&#xff…

ky10 server x86 安装、更新openssl3.1.4(在线编译安装、离线安装)

查看openssl版本 openssl version 离线编译安装升级 #!/bin/shOPENSSLVER3.1.4OPENSSL_Vopenssl versionecho "当前OpenSSL 版本 ${OPENSSL_V}" #------------------------------------------------ #wget https://www.openssl.org/source/openssl-3.1.4.tar.gzech…

异步操作的方法

在高级语言中已经有了异步的原语言&#xff0c;而在C 中的最好的方式就是 libevent 的方式,我这还是相当认同的&#xff0c;高级语言就不需要在苦哈哈的&#xff0c;事件转圈了&#xff0c;但是原理还是以事件为基础的 一句话就是在一个循环中等着他执行完,这个循环中有很多其他…

XML映射文件

<?xml version"1.0" encoding"UTF-8" ?> <!DOCTYPE mapperPUBLIC "-//mybatis.org//DTD Mapper 3.0//EN""http://mybatis.org/dtd/mybatis-3-mapper.dtd"> <mapper namespace"org.mybatis.example.BlogMapper&q…

电子学会C/C++编程等级考试2021年06月(二级)真题解析

C/C++等级考试(1~8级)全部真题・点这里 第1题:数字放大 给定一个整数序列以及放大倍数x,将序列中每个整数放大x倍后输出。 时间限制:1000 内存限制:65536输入 包含三行: 第一行为N,表示整数序列的长度(N ≤ 100); 第二行为N个整数(不超过整型范围),整数之间以一个空格…

Python三百行代码实现一简约个人博客网站(全网最小巧)

这是全互联网最小巧的博客&#xff0c;没有比这更小的了。虽然小巧&#xff0c;但功能一点儿也不弱&#xff0c;支持文章的分页展示&#xff0c;文章表格&#xff0c;图片和代码语法高亮。文章无限制分类&#xff0c;访问量统计&#xff0c;按时间和按点击量排序&#xff0c;展…

【matlab程序】南海土台风画法

【matlab程序】南海土台风画法 图片 往期推荐 图片 【python海洋专题一】查看数据nc文件的属性并输出属性到txt文件 【python海洋专题二】读取水深nc文件并水深地形图 【python海洋专题三】图像修饰之画布和坐标轴 【Python海洋专题四】之水深地图图像修饰 【Python海洋专…

将图像的rgb数据转成DICOM医学图像格式

dcmtk官方文档&#xff1a;https://support.dcmtk.org/docs/ dcmtk最新源码下载&#xff1a;https://www.dcmtk.org/en/dcmtk/dcmtk-software-development/ dcmtk旧版本源码下载&#xff1a;https://dicom.offis.de/download/dcmtk/ 用DCMTK库实现将图像转成dcm格式 dcmtk库的…