当前位置: 首页 > 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…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...