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

leetcode 704. 二分查找

  • 题目描述
  • 解题思路
  • 执行结果
leetcode 704. 二分查找


题目描述

  1. 二分查找

给定一个 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]之间。

来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/binary-search 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

法1

方法1:二分法
题目已经描述得很清楚了,使用二分法查找数,二分法也非常适用于这种排序的数组,对时间有很多优化

具体实现方法如下:

我们使用二分查找算法来搜索目标值。

  1. 首先,我们将数组的左边界 left 设置为 0,右边界 right 设置为数组长度减 1。
  2. 然后,我们在每一步迭代中计算中间元素的下标 mid。如果 nums[mid] 等于目标值 target,则返回 mid。如果 nums[mid] 小于目标值 target,则更新 left 为 mid + 1,表示目标值可能在右半部分。如果 nums[mid] 大于目标值 target,则更新 right 为 mid - 1,表示目标值可能在左半部分。当 left 大于 right 时,表示目标值不存在于数组中,因此返回 -1。
  • 时间复杂度(O(logn))
  • 空间复杂度(O(1))

执行结果

法1

func search(nums []int, target int) int {
 left, right := 0len(nums)-1

 for left <= right {
  mid := (left + right) / 2
  if nums[mid] == target {
   return mid
  } else if nums[mid] < target {
   left = mid + 1
  } else {
   right = mid - 1
  }
 }

 return -1
}

执行结果: 通过 显示详情 查看示例代码 添加备注

执行用时: 20 ms , 在所有 Go 提交中击败了 99.64% 的用户 内存消耗: 6.5 MB , 在所有 Go 提交中击败了 69.89% 的用户 通过测试用例: 47 / 47 炫耀一下:

法2


法3


本文由 mdnice 多平台发布

相关文章:

leetcode 704. 二分查找

题目描述解题思路执行结果 leetcode 704. 二分查找 题目描述 二分查找 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;写一个函数搜索 nums 中的 target&#xff0c;如果目标值存在返回下标&#xff0c;否则返回 -1。 示…...

蓝牙耳机什么牌子好?500内好用的蓝牙耳机推荐

随着蓝牙耳机的受欢迎程度越来越高&#xff0c;近几年来&#xff0c;无蓝牙耳机市场呈爆发式增长&#xff0c;蓝牙耳机品牌也越来越多。那么蓝牙耳机什么牌子好&#xff1f;接下来&#xff0c;我来给大家推荐几款500内好用的蓝牙耳机&#xff0c;一起来看看吧。 一、南卡小音舱…...

设计模式 -- 中介者模式

前言 月是一轮明镜,晶莹剔透,代表着一张白纸(啥也不懂) 央是一片海洋,海乃百川,代表着一块海绵(吸纳万物) 泽是一柄利剑,千锤百炼,代表着千百锤炼(输入输出) 月央泽,学习的一种过程,从白纸->吸收各种知识->不断输入输出变成自己的内容 希望大家一起坚持这个过程,也同…...

人工智能的未来之路:语音识别的应用与挑战

随着人工智能技术的不断发展&#xff0c;语音识别已成为人工智能领域的一个重要应用。语音识别是指通过计算机对语音信号进行处理&#xff0c;将其转换为可以被计算机识别的文本或指令的过程。语音识别技术的应用范围非常广泛&#xff0c;例如智能家居、语音助手、智能客服、智…...

c++ 友元介绍

友元的目的就是让一个函数或类访问另一个函数中的私有成员 友元函数 &#xff08;1&#xff09;普通函数作为友元函数 class 类名{friend 函数返回值类型 友元函数名(形参列表);//这个形参一般是此类的对象.... } 经过以上操作后&#xff0c;友元函数就可以访问此类中的私有…...

四维轻云地理空间数据在线管理软件能够在线管理哪些数据?

四维轻云是一款地理空间数据在线管理软件&#xff0c;支持各类地理空间数据的在线管理、浏览及分享&#xff0c;用户可不受时间地点限制&#xff0c;随时随地查看各类地理空间数据。软件还具有项目管理、场景搭建、素材库等功能模块&#xff0c;支持在线协作管理&#xff0c;便…...

学习 GitHub 对我们有什么好处?

学习 GitHub 对我们有什么好处&#xff1f; 为什么要学习 GitHub&#xff0c;或者说学习 GitHub 对我们有什么好处&#xff1f; 理由一&#xff1a;GitHub 上有很多大牛出没&#xff0c;国外的咱先不说&#xff0c;就国内的像百度、腾讯、阿里之类的大公司&#xff0c;里面的很…...

java记录-反射

什么是反射 反射是一种让Java拥有一定动态性的机制&#xff0c;它允许程序在执行期间取得任何类的内部信息&#xff0c;并且直接操作任意对象的内部属性及方法 类加载 类加载后通过堆内存方法区的Class类型对象就能了解该类的结构信息&#xff0c;这个对象就像该类的一面镜子…...

这次彻底不需要账号了,无需魔法永久白嫖GPT

免费GPT 自GPT风靡以来&#xff0c;大家用的是不亦乐乎&#xff0c;你用他去解决过实际问题&#xff0c;你用他去写过代码&#xff0c;你用他去修改过bug&#xff0c;你用他去写过sql&#xff0c;你用他去画过图&#xff0c;你问过他你能想到的任何“刁钻”问题。 你&#xff…...

远程桌面连接是什么?如何开启远程桌面连接详细教程

远程桌面连接是一种非常方便的技术&#xff0c;它允许用户通过互联网在不同的计算机之间共享资源和访问数据。目前这个技术已经广泛地应用于企业、教育、医疗和其他领域&#xff0c;使得人们能够更高效地工作和学习。 这篇文章&#xff0c;我将解释远程桌面连接是什么&#xf…...

lua实战(2)

目录 值和类型子类型类型字符串type (v) 值和类型 Lua是一种动态类型语言。这意味着变量没有类型;只有价值观才有意义。该语言中没有类型定义。所有值都有自己的类型。 Lua中的所有值都是一等值。这意味着所有的值都可以存储在变量中&#xff0c;作为参数传递给其他函数&…...

UI自动化测试案例——简单的Google搜索测试

以下是一个UI自动化测试的经典案例&#xff1a; import unittest from selenium import webdriverclass GoogleSearchTest(unittest.TestCase):def setUp(self):# 创建Chrome浏览器实例self.driver webdriver.Chrome()self.driver.maximize_window() # 最大化浏览器窗口def t…...

C++之虚函数原理

对象数据和函数的存储方式 注意说的是对象。 C中的对象存储方式是 每个对象占用的存储空间只是该对象的数据部分&#xff08;虚函数指针和虚基类指针也属于数据部分&#xff09;&#xff0c;函数属于公共部分。 虚函数表 虚函数是通过虚函数表实现的。 C实现虚函数的方法是…...

Windows Information Protection(WIP)部署方案

目录 前言 一、方案准备工作 1、确定哪些数据需要保护 2、选择合适的加密方式...

细说Hibernate的缓存机制

Hibernate 的缓存机制主要包括一级缓存和二级缓存。 1. 一级缓存&#xff08;Session 缓存&#xff09;&#xff1a; 一级缓存是 Hibernate 的 Session 级别的缓存&#xff0c;与每个 Session 对象相关联。当您通过 Session 对象执行查询、保存或更新操作时&#xff0c;Hibern…...

初识C++之线程库

目录 一、C中的线程使用 二、C的线程安全问题 1. 加锁 2. 变为原子操作 3. 递归里面的锁 4. 定时锁 5. RAII的锁 三、条件变量 1. 为什么需要条件变量 2. 条件变量的使用 2.1 条件变量的相关函数 2.2 wait函数 一、C中的线程使用 线程的概念在linux中的线程栏已经…...

ChatGLM-LLaMA-chinese-insturct 学习记录(含LoRA的源码理解)

ChatGLM-LLaMA-chinese-insturct 前言一、实验记录1.1 环境配置1.2 代码理解1.2.1 LoRA 1.4 实验结果 二、总结 前言 介绍&#xff1a;探索中文instruct数据在ChatGLM, LLaMA等LLM上微调表现&#xff0c;结合PEFT等方法降低资源需求。 Github: https://github.com/27182812/Ch…...

JuiceFS-K8s部署

目录 1、部署JuiceFS-CSI驱动2、创建OBS认证信息Secret3、创建存储类4、创建PVC--PVC创建时会自动创建PV5、创建测试Pod--测试Pod创建容器内是否挂载成功 官网文档地址&#xff1a;https://juicefs.com/docs/zh/csi/introduction/ 1、部署JuiceFS-CSI驱动 部署yaml如下&#x…...

2023最新版本Camtasia电脑录屏软件好不好用?

在当今数字化时代&#xff0c;屏幕录制成为了许多用户制作教学视频、演示文稿、游戏攻略等内容的首选。本文将为您介绍几款常用的电脑录屏软件&#xff0c;包括Camtasia、OBS Studio、Bandicam等&#xff0c;并对其进行功能和用户体验方面的比较&#xff0c;同时给出10款电脑录…...

第三章 Linux 初步

第三章 Linux 初步 一、 基本操作 ①登录&#xff1a; Linux 是多用户系统&#xff0c;必须用正确的用户名和口令登录后才能 进入 Linux Shell 提示符状态。 默认的文本界面 Shell 提示符有两种&#xff1a; •root 用户登录后的提示符&#xff1a; # •普通用户登录后的…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

多元隐函数 偏导公式

我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式&#xff0c;给定一个隐函数关系&#xff1a; F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 &#x1f9e0; 目标&#xff1a; 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z​、 …...

【若依】框架项目部署笔记

参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作&#xff1a; 压缩包下载&#xff1a;http://download.redis.io/releases 1. 上传压缩包&#xff0c;并进入压缩包所在目录&#xff0c;解压到目标…...