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

代码随想录——二分查找(一)

模版

func BinarySearch(nums *int,target int){l,r:=0,len(nums)-1for l<=r{mid:=l+(r-l)/2if nums[mid]==target{return mid}else if nums[mid]<target{l=mid+1}else{r=mid-1}}return -1
}

特点

  • 查找条件可以在不与元素的两侧进行比较的情况下确定(或使用它周围的特定元素)。
  • 不需要后处理,因为每一步中,你都在检查是否找到了元素。如果到达末尾,则知道未找到该元素。

例题

一.Leetcode69——x的平方根

在这里插入图片描述
解题代码:

func mySqrt(x int) int {if x==0{return x}l,r:=0,xans:=-1for l<=r{mid:=l+(r-l)/2if mid*mid>x{r=mid-1}else{ans=midl=mid+1}}return ans
}

二.猜数字大小

在这里插入图片描述

func guessNumber(n int) int {l,r:=1,nfor l<=r{mid:=(r-l)/2+lif guess(mid)==0{return mid}else if guess(mid)==-1{r=mid-1}else{l=mid+1}}return -1
}

三.搜索旋转排序数组

在这里插入图片描述
解析:
这道题要求的时间复杂度是O(logn),这注定我们不能遍历这一个数组,所以我们不能暴力解题,我们可以观察这个旋转数组,由于它已经经过了一次排序,所以它虽然不是全局有序但是至少局部有序,所以我们可以尝试稍微修改二分查找的条件来适应这种情况,因为排过序所以其实它还是可以分为两个局部有序的子数组,所以我们可以根据这个对数组进行处理,如下图:
图片来自于leetcode题解
示例代码如下:

func search(nums []int, target int) int {n:=len(nums)if n==0{return -1}if n==1{if target==nums[0]{return 0}else{return -1}}l,r:=0,n-1for l<=r{mid:=(r-l)/2+lif target==nums[mid]{return mid}if nums[l]<=nums[mid]{if nums[l]<=target && target<nums[mid]{r=mid-1}else{l=mid+1}}else if nums[r]>nums[mid]{if nums[r]>=target && target>nums[mid]{l=mid+1}else{r=mid-1}}}return -1
}

相关文章:

代码随想录——二分查找(一)

模版 func BinarySearch(nums *int,target int){l,r:0,len(nums)-1for l<r{mid:l(r-l)/2if nums[mid]target{return mid}else if nums[mid]<target{lmid1}else{rmid-1}}return -1 }特点 查找条件可以在不与元素的两侧进行比较的情况下确定&#xff08;或使用它周围的特…...

【NLP】多标签分类【下】

文章目录 简介个人博客与相关链接1 实验数据与任务说明2 模型介绍2.1 TransformerTransformer能做什么&#xff1f; 2.2 Hugging FaceHugging Face的Transformers库社区支持和资源预训练模型的应用 2.3 T5模型&#xff08;Text-To-Text Transfer Transformer&#xff09;T5的核…...

HWOD:密码强度等级

一、知识点 回车键的ASCII码是10 如果使用EOF&#xff0c;有些用例不通过 二、题目 1、描述 密码按如下规则进行计分&#xff0c;并根据不同的得分为密码进行安全等级划分。 一、密码长度: 5 分: 小于等于4 个字符 10 分: 5 到7 字符 25 分: 大于等于8 个字符 二、字母: 0…...

期货学习笔记-MACD指标学习2

MACD底背离把握买入多单的技巧 底背离的概念及特征 底背离指的是MACD指标与价格低点之间的对比关系&#xff0c;这里需要明白的是MACD指标的涨跌动能和价格形态衰竭形态之间的关系&#xff0c;如果市场价格创新低而出现衰竭形态同时也有底背离形态的出现&#xff0c;此时下跌…...

5G智慧港口简介(一)

引言 港口作为交通运输的枢纽,在促进国际贸易和地区发展中起着举足轻重的作用,全球贸易中约 90% 的贸易由海运业承载,作业效率对于港口至关重要。在“工业 4.0”、“互联网 +”大发展的时代背景下,港口也在进行数字化、全自动的转型升级。随着全球 5G 技术浪潮的到来,华为…...

订单中台架构:打造高效订单管理系统的关键

在现代商业环境下&#xff0c;订单管理对于企业来说是至关重要的一环。然而&#xff0c;随着业务规模的扩大和多渠道销售的普及&#xff0c;传统的订单管理方式往往面临着诸多挑战&#xff0c;如订单流程复杂、信息孤岛、数据不一致等问题。为了应对这些挑战并抓住订单管理的机…...

【算法】模拟

个人主页 &#xff1a; zxctscl 如有转载请先通知 题目 前言1. 1576. 替换所有的问号1.1 分析1.2 代码 2. 495. 提莫攻击2.1 分析2.2 代码 3. 6. Z 字形变换3.1 分析3.2 代码 4. 38. 外观数列4.1 分析4.2 代码 5. 1419. 数青蛙5.1 分析5.2 代码 前言 模拟算法就是根据题目所给…...

电力综合自动化系统对电力储能技术的影响有哪些?

电力综合自动化系统对电力储能技术的影响主要体现在以下几个方面&#xff1a; 提高能源利用效率&#xff1a;电力综合自动化系统通过优化调度和能量管理&#xff0c;可以实现储能设备的有效利用&#xff0c;提高能源利用效率。在电力系统中&#xff0c;储能设备可以有效地平抑风…...

Compose UI 之 Card 卡片组件

Card Card 是用于显示带有圆角和可选阴影的矩形内容容器。它通常用于构建用户界面,并可以包含标题、文本、图像、按钮等元素,表示界面上的可交互元素,我们称它是 “卡片”。 Card 使用的一些经典的场景: 列表数据,例如 新闻列表,产品列表等。信息提示框,使用 Card 组件…...

ELK日志

​​​​​​​...

WPF Pack

在WPF中&#xff0c;Pack URI&#xff08;Uniform Resource Identifier&#xff09;是一种特殊格式的统一资源标识符&#xff0c;用于定位和访问应用程序内部或外部的各种资源&#xff0c;如XAML文件、图像、样式、字体等。这种机制允许开发者以标准化、平台无关的方式引用和打…...

计算两个时间段的差值

计算两个时间段的差值 运行效果&#xff1a; 代码实现&#xff1a; #include<stdio.h>typedef struct {int h; // 时int m; // 分int s; // 秒 }Time;void fun(Time T[2], Time& diff) {int sum_s[2] { 0 }; for (int i 0; i < 1; i) { // 统一为秒数sum_s[…...

Element Plus 表单校验

原理 为 rules 属性传入约定的验证规则&#xff0c;并将 form-Item 的 prop 属性设置为需要验证的特殊键值:model和:rules中字段的名称需要一致 示例&#xff1a; <template><el-form ref"ruleFormRef" :model"ruleForm" :rules"rules&q…...

java实现TCP交互

服务器端 import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.net.ServerSocket; import java.net.Socket; import java.util.PriorityQueue; import java.util.Scanner;public class TCP_Serv…...

学习云计算HCIE选择誉天有什么优势?

誉天云计算课程优势实战性强 课程注重实践操作&#xff0c;通过实际案例和实验操作&#xff0c;让学员深入了解云计算的应用场景和实际操作技能。课程内容全面 涵盖所有云计算涉及的IT基础知识、服务器、存储、网络等方面的基础知识&#xff0c;开源操作系统Linux&#xff0c;开…...

python之文件操作与管理

1、文件操作 通过open&#xff08;&#xff09;操作&#xff0c;来创建文件对象&#xff0c;下面是open&#xff08;&#xff09;函数语法如下&#xff1a; open&#xff08;file,mode r,buffering -1 , encoding None ,errors None , newline None,closefd True,opener …...

大厂Java笔试题之对完全数的处理

题目&#xff1a;完全数&#xff08;Perfect number&#xff09;&#xff0c;又称完美数或完备数&#xff0c;是一些特殊的自然数。 它所有的真因子&#xff08;即除了自身以外的约数&#xff09;的和&#xff08;即因子函数&#xff09;&#xff0c;恰好等于它本身。 例如&…...

【Redis深度解析】揭秘Cluster(集群):原理、机制与实战优化

Redis Cluster是Redis官方提供的分布式解决方案&#xff0c;通过数据分片与节点间通信机制&#xff0c;实现了水平扩展、高可用与数据容灾。本文将深入剖析Redis Cluster的工作原理、核心机制&#xff0c;并结合实战经验分享优化策略&#xff0c;为您打造坚实可靠的Redis分布式…...

【JAVA基础篇教学】第六篇:Java异常处理

博主打算从0-1讲解下java基础教学&#xff0c;今天教学第五篇&#xff1a; Java异常处理。 异常处理是Java编程中重要的一部分&#xff0c;它允许开发人员在程序运行时检测和处理各种错误情况&#xff0c;以保证程序的稳定性和可靠性。在Java中&#xff0c;异常被表示为对象&am…...

【ubuntu20.04】安装GeographicLib

下载地址 GeographicLib: Installing GeographicLib 我们是ubuntu20.04 &#xff0c;所以下载第一个 GeographicLib-2.3.tar.gz 接着跟着官方步骤安装&#xff0c;会出错&#xff01;&#xff01;&#xff01;&#xff01;马的 官方错误示例&#xff1a;tar xfpz Geographi…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权

摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题&#xff1a;安全。文章将详细阐述认证&#xff08;Authentication) 与授权&#xff08;Authorization的核心概念&#xff0c;对比传统 Session-Cookie 与现代 JWT&#xff08;JS…...

第八部分:阶段项目 6:构建 React 前端应用

现在&#xff0c;是时候将你学到的 React 基础知识付诸实践&#xff0c;构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段&#xff0c;你可以先使用模拟数据&#xff0c;或者如果你的后端 API&#xff08;阶段项目 5&#xff09;已经搭建好&#xff0c;可以直接连…...

Unity VR/MR开发-VR开发与传统3D开发的差异

视频讲解链接&#xff1a;【XR马斯维】VR/MR开发与传统3D开发的差异【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...