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

704. 二分查找

Problem: 704. 二分查找

🐷我的leetcode主页

文章目录

  • 题目
  • 分类
  • 思路
    • 什么是二分查找
    • 如何理解时间复杂度
  • 解题方法
    • Code

题目

给定一个 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
提示:

  1. 你可以假设 nums 中的所有元素是不重复的。

  2. n 将在 [1, 10000]之间。

  3. nums 的每个元素都将在 [-9999, 9999]之间。

分类

二分查找

思路

什么是二分查找

二分查找是一种查找算法,它的基本思想是:通过比较元素的大小来缩小查找范围,直到找到目标元素或查找范围为空。

场景样例:

  1. 假设要在电话簿中找一个名字以 K 打头的人,(现在谁还用电话簿!)可以从头开始翻页,直到进入以 K 打头的部分。但你很可能不这样做,而是从中间开始,因为你知道以 K 打头的名字在电话簿中间。所以你会直接从中间开始找。

  2. 两个人玩游戏,A想一个1-100的数字(比如是60),B来猜。

如果B从1开始猜,一直猜到99才能猜到,那么时间复杂度是O(n)

如果B从50开始猜,A会告诉B猜小了,那么B肯定会在50-100里面猜,那么就排除了一半1-50的数字

B再从75开始猜,A会告诉B猜大了,下次一B肯定在50-75里面猜,又排除了一半75-100的数字

这样依次类推,最终最多猜测O(logn)次,就能猜到最终共的答案。

如何理解时间复杂度

大 O 表示法指出了最糟情况下的运行时间

比如上面的例子,1-100采用线性放大依次猜,猜到100才能猜对的话,那么就需要猜测n次,所以复杂度是O(n);
如果采用二分查找,那么最多需要猜测100对2取对数的次数,那么时间复杂度是O(logn)。

通俗理解的话可以理解为操作数

比如要在一张正方形的纸上面画16个格子,那么最坏情况下,一个一个画,需要画16次,所以时间复杂度是O(n)。

如果采用折叠的方式,对折一次,产生2个格子,两次产生4个格子,3次产生8个格子,4次产生16个格子,那么时间复杂度是O(logn)。

解题方法

Code

    def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""low = 0high = len(nums) - 1while low <= high:mid = (low + high) // 2if nums[mid] == target:return midelif nums[mid] < target:low = mid + 1else:high = mid - 1return -1

相关文章:

704. 二分查找

Problem: 704. 二分查找 &#x1f437;我的leetcode主页 文章目录 题目分类思路什么是二分查找如何理解时间复杂度 解题方法Code 题目 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;写一个函数搜索 nums 中的 target&a…...

php回车变br、php显示br

在 PHP 中&#xff0c;如果你想将回车符&#xff08;\n&#xff09;转换为 HTML 的 <br> 标签来实现换行显示&#xff0c;可以使用内置函数 nl2br()。这个函数会将文本中的换行符替换为 <br> 标签。以下是使用 nl2br() 函数的示例代码&#xff1a; <?php $tex…...

找最大数字-第12届蓝桥杯国赛Python真题解析

[导读]&#xff1a;超平老师的Scratch蓝桥杯真题解读系列在推出之后&#xff0c;受到了广大老师和家长的好评&#xff0c;非常感谢各位的认可和厚爱。作为回馈&#xff0c;超平老师计划推出《Python蓝桥杯真题解析100讲》&#xff0c;这是解读系列的第60讲。 找最大数字&#…...

蓝桥杯 算法提高 ADV-1170 阶乘测试 python AC

找规律题&#xff0c;遍历i中有几个m就加几&#xff0c;和m的多少次数有关 第一版&#x1f447; try:while True:n, m map(int, input().split())ll [i for i in range(1, n 1) if i % m 0]ans len(ll)M mwhile ll:lll []M * mfor i in ll:if i % M 0:lll.append(i)a…...

阿里巴巴杭州全球总部正式启用,创新“减碳大脑”科技减碳 | 最新快讯

来源&#xff1a;封面新闻 封面新闻记者付文超 5 月 10 日&#xff0c;记者获悉&#xff0c;位于未来科技城的阿里巴巴杭州全球总部新园区正式启用&#xff0c;这是阿里巴巴目前最大的综合性办公园区。从空中俯瞰&#xff0c;园区正中央呈现阿里标志性的笑脸 logo&#xff0c;这…...

蓝桥杯国赛练习题真题Java(矩阵计数)

题目描述 一个 NM 的方格矩阵&#xff0c;每一个方格中包含一个字符 O 或者字符 X。 要求矩阵中不存在连续一行 3 个 X 或者连续一列 3 个 X。 问这样的矩阵一共有多少种&#xff1f; 输入描述 输入一行包含两个整数 N,M (1≤N,M≤5)。 输出描述 输出一个整数代表答案。…...

概念解析 | ROC曲线:评估分类模型

注1:本文系"概念解析"系列之一,致力于简洁清晰地解释、辨析复杂而专业的概念。本次辨析的概念是:ROC曲线的含义和绘制 概念解析 | ROC曲线:评估分类模型 第一部分:通俗解释 在我们的日常生活中,经常会遇到需要做出判断和选择的情况。比如,当你收到一封邮件时…...

数据可视化训练第二天(对比Python与numpy中的ndarray的效率并且可视化表示)

绪论 千里之行始于足下&#xff1b;继续坚持 1.对比Python和numpy的性能 使用魔法指令%timeit进行对比 需求&#xff1a; 实现两个数组的加法数组 A 是 0 到 N-1 数字的平方数组 B 是 0 到 N-1 数字的立方 import numpy as np def numpy_sum(text_num):"""…...

【Java EE】数据库连接池详解

文章目录 &#x1f38d;数据库连接池&#x1f338;Hikari&#x1f338;Druid &#x1f340;MySQL开发企业规范⭕总结 &#x1f38d;数据库连接池 在上⾯Mybatis的讲解中,我们使⽤了数据库连接池技术,避免频繁的创建连接,销毁连接 下⾯我们来了解下数据库连接池 数据库连接池负…...

正点原子[第二期]Linux之ARM(MX6U)裸机篇学习笔记-15.4讲 GPIO中断实验-IRQ中断服务函数详解

前言&#xff1a; 本文是根据哔哩哔哩网站上“正点原子[第二期]Linux之ARM&#xff08;MX6U&#xff09;裸机篇”视频的学习笔记&#xff0c;在这里会记录下正点原子 I.MX6ULL 开发板的配套视频教程所作的实验和学习笔记内容。本文大量引用了正点原子教学视频和链接中的内容。…...

如何平衡RPA机器人的安全性与业务敏捷性,同时不牺牲用户体验?

平衡RPA机器人的安全性与业务敏捷性&#xff0c;同时不牺牲用户体验&#xff0c;是RPA实施中的一个关键挑战。以下是一些策略和最佳实践&#xff1a; ### 1. 安全设计原则 从设计阶段就将安全性纳入考虑&#xff0c;遵循安全设计原则。这意味着在开发RPA解决方案时&#xff0…...

地球行星UE5和UE4

地球行星&#xff0c;包含多种地球风格&#xff0c;可蓝图控制自转和停止&#xff0c;可材质自转. 支持版本4.21-5.4版本 下载位置&#xff1a;https://mbd.pub/o/bread/ZpWZm5lv b站工坊&#xff1a;https://gf.bilibili.com/item/detail/1105582041 _______________________…...

7.k8s中的名称空间namespace

目录 一、Namespace(命名空间) 二、查看系统的名称空间 1.查看系统中的名称空间列表 2.单独查看一个名称空间下的对应资源 三、名称空间的管理 1.创建名称空间 1.1响应式创建 1.2声明式创建 2.删除名称空间 四、资源引用名称空间 一、Namespace(命名空间) 命名空间(Name…...

上海企业源代码防泄密解决方案,企业源代码防泄密如何应对?

随之互联网的发展&#xff0c;企业员工因离职把企业源代码泄露或删库跑路的事情屡见不鲜&#xff0c;各大互联网公司基本都会出现源代码泄露的事情&#xff0c;这样的问题也成了企业在发展过程中不可避免的问题。企业源代码泄露会给企业带来的损失也是不可估量的&#xff0c;据…...

将要上市的自动驾驶新书《自动驾驶系统开发》中摘录各章片段 4

第十三章 车联网 数字化设备正变得越来越普遍并且相互联系。这些设备向数字生态系统智能部分的演进创造了迄今为止尚未解决安全问题的新颖应用。一个特定的例子是车辆&#xff0c;随着车辆从简单的交通方式发展到具有新的感知和通讯功能的智能实体&#xff0c;就成为智能城市的…...

OpenSearch 与 Elasticsearch:7 个主要差异及如何选择

OpenSearch 与 Elasticsearch&#xff1a;7 个主要差异及如何选择 1. 什么是 Elasticsearch&#xff1f; Elasticsearch 是一个基于 Apache Lucene 构建的开源、RESTful、分布式搜索和分析引擎。它旨在处理大量数据&#xff0c;使其成为日志和事件数据管理的流行选择。 Elasti…...

[Docker]容器的网络类型以及云计算

目录 知识梗概 1、常用命令2 2、容器的网络类型 3、云计算 4、云计算服务的几种主要模式 知识梗概 1、常用命令2 上一篇已经学了一些常用的命令&#xff0c;这里补充两个&#xff1a; 导出镜像文件&#xff1a;[rootdocker ~]# docker save -o nginx.tar nginx:laster 导…...

VMP 简单源码分析(.net)

虚拟机 获取CPU的型号 实现了一个指令集解释器&#xff0c;每个操作码对应一个特定的处理函数&#xff0c;用于执行相应的指令操作。在执行字节码时&#xff0c;解释器会根据操作码查找并调用相应的处理函数来执行指令。 截获异常 先由虚拟机处理 处理不了再抛出异常 priva…...

数据结构与算法学习笔记-二叉树的顺序存储表示法和实现(C语言)

目录 前言 1.数组和结构体相关的一些知识 1.数组 2.结构体数组 2.二叉树的顺序存储表示法和实现 1.定义 2.初始化 3.先序遍历二叉树 4.中序遍历二叉树 5.后序遍历二叉树 6.完整代码 前言 二叉树的非递归的表示和实现。 1.数组和结构体相关的一些知识 1.数组 在C语…...

如何在Windows和Linux中杀死Python进程

在开发和运行Python脚本的过程中&#xff0c;有时我们需要强制结束正在运行的Python进程。这可能是因为脚本运行出现了不可预见的错误&#xff0c;或者我们需要停止一个长时间执行的任务。无论原因如何&#xff0c;了解如何在不同操作系统中正确、安全地终止Python进程都是一项…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...