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

代码随想录刷题-数组-二分查找

文章目录

  • 写在前面
  • 原理
  • 习题
    • 题目1
      • 思路和代码
    • 题目-2

写在前面

这个专栏是记录我刷代码随想录过程中的随想和总结。每一小节都是根据自己的理解撰写的,文章比较短,主要是为了记录和督促自己。刷完一章后,我会再单独整理一篇文章来总结和分享。

本节对应代码随想录中:代码随想录-二分查找

原理

二分法(Binary Search)是一种在有序数组中查找特定元素的算法。它的原理是,将数组分成两半,然后判断目标元素在哪一半中,然后再继续将这一半分成两半,直到找到目标元素或者确定目标元素不存在为止。

前提条件:二分法适用于有序数组或有序列表中的查找操作,且元素必须支持比较操作。

一旦有重复元素的时候,二分法返回的下标可能不唯一

算法步骤如下:

1.将数组按照中间元素分成两部分。

2.如果中间元素等于目标元素,直接返回中间元素的下标。

3.如果中间元素大于目标元素,说明目标元素在左半部分,将右边界移动到中间元素的左边。

4.如果中间元素小于目标元素,说明目标元素在右半部分,将左边界移动到中间元素的右边。

5.重复以上步骤,直到找到目标元素或者确定目标元素不存在。

习题

题目1

704. 二分查找
给定一个 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]之间。

思路和代码

这道题目说了元素是有序的,而且无重复元素,那么在查找的时候就可以使用二分法进行查找

写二分法会遇到三种情况

  • 初始 right = nums.size()-1 还是 nums.size()
  • right = middle-1 还是 right = middle
  • while(left <= right) 还是 while(left < right)

如下面这张图,left 等不等于 right,right 的取值也会不一样,可分为两种写法
在这里插入图片描述

  • 如果初始写 right=nums.size()-1 即7个元素中 L=0,R=6,那么查找区间就是[0,6],M 为3。
  • 此时应该写 right = middle-1 。如上图 M=3时没有匹配成功,那么下次的区间应该是[0,2],因为 M=3已经判断一次了
  • 如上图如果 M=1时仍不是我们要找的元素,假如此时还是大于待查找元素,那么 R=0。此时 left=right=0是有意义的,也就是我们需要最后判定下 L=0时的1是不是待查找元素,因此 while 的条件为 while(left <= right)

这三种情况其实就是要互相对应,第二种类型在代码随想录中有解释

代码如下

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1; // 定义target在左闭右闭的区间里,[left, right]while (left <= right) { // 当left==right,区间[left, right]依然有效,所以用 <=int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2if (nums[middle] > target) {right = middle - 1; // target 在左区间,所以[left, middle - 1]} else if (nums[middle] < target) {left = middle + 1; // target 在右区间,所以[middle + 1, right]} else { // nums[middle] == targetreturn middle; // 数组中找到目标值,直接返回下标}}// 未找到目标值return -1;}
};

注意取中间值时没有使用 middle = (left + right) / 2 而是 middle = left + ((right - left) / 2)

这样写能够避免 left + right 可能数值太大导致溢出的问题

例子:在闭区间[3,9]中 right-left=6,说明3到9需要走6步,再除2得3,说明从3到9走3步可以走到中间的位置

题目-2

35.搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4

提示:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104

代码如下

class Solution {public:int searchInsert(vector<int>& nums, int target) {int n = nums.size();int left = 0, right = n - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {right = right - 1;} else {left = left + 1;}}return left;}
};

观察上述代码可以发现这题和上题只是在上题 return -1 处改成了 return left

解释: 上题的 return -1 和这里的 return left 都代表着所查找元素没有出现给定数组中的情况

至于目标值被插入的顺序为什么是 left。根据 if 的判断条件,left 左边的值一直保持小于 target,right 右边的值一直保持大于等于 target,而且 left 最终一定等于 right+1

  • 左边:[2,4]查找1,left=0,right=1,一轮后 left=0,right=-1
  • 中间:[2,4]查找3,left=0,right=1,一轮后 left=1,right=1,二轮后 left=1,right=0
  • 右边:[2,4]查找5,left=0,right=1,一轮后 left=1,right=1,二轮后 left=2,right=1

当 left=right=middle 时,若仍未找到,此时要么 right-- 要么 left++,最终一定是 left=right+1

这么一来,循环结束后,left 左边的部分全部小于 target,所以最终答案一定在 left 的位置

参考:搜索插入位置- 力扣(LeetCode)

相关文章:

代码随想录刷题-数组-二分查找

文章目录写在前面原理习题题目1思路和代码题目-2写在前面 这个专栏是记录我刷代码随想录过程中的随想和总结。每一小节都是根据自己的理解撰写的&#xff0c;文章比较短&#xff0c;主要是为了记录和督促自己。刷完一章后&#xff0c;我会再单独整理一篇文章来总结和分享。 本…...

HCIA复习1

HCIA复习 抽象语言---->编码 编码---->二进制 二进制--->电信号 处理电信号 OSI参考模型----OSI/RM 应用层 表示层 会话层 传输层 端口号&#xff1a;0-65535&#xff1b;1-1023是注明端口 网络层 IP地址 数据链路层 物理层 ARP协议 正向ARP---通过IP地址获取目的MAC地…...

Kotlin中的destructuring解构声明

开发中有时只是想分解一个包含多个字段的对象来初始化几个单独的变量。要实现这一点&#xff0c;可以使用Kotlin的解构声明。本文主要了解&#xff1a;“1、如何使用解构声明这种特性 2、底层是如何实现的 3、如何在你自己的类中实现它1、解构声明的使用解构声明&a…...

Kubernetes Pod 水平自动伸缩(HPA)

Pod 自动扩缩容 之前提到过通过手工执行kubectl scale命令和在Dashboard上操作可以实现Pod的扩缩容&#xff0c;但是这样毕竟需要每次去手工操作一次&#xff0c;而且指不定什么时候业务请求量就很大了&#xff0c;所以如果不能做到自动化的去扩缩容的话&#xff0c;这也是一个…...

钉钉、企业微信和飞书向“钱”看

在急剧变革的时候&#xff0c;不管黑猫白猫&#xff0c;要抓到老鼠才算好猫。如今&#xff0c;各互联网企业早已进入降本增效的新阶段。勒紧裤腰带过日子之下&#xff0c;能不能盈利、商业化空间有多大&#xff0c;就成为各个业务极为重要的考核指标。在各业务板块中&#xff0…...

网上购物网站的设计

技术&#xff1a;Java、JSP等摘要&#xff1a;本文介绍了JSP和JAVA等相关技术&#xff0c;针对网上购物系统的实际需求&#xff0c;设计开发了一个基于JSP的小型电子商务网站也就是网上购物系统&#xff0c;。在设计开发中&#xff0c;采用的是SSH框架&#xff08;strutsspring…...

【Java学习笔记】8.Java 运算符

Java 运算符 计算机的最基本用途之一就是执行数学运算&#xff0c;作为一门计算机语言&#xff0c;Java也提供了一套丰富的运算符来操纵变量。我们可以把运算符分成以下几组&#xff1a; 算术运算符关系运算符位运算符逻辑运算符赋值运算符其他运算符 算术运算符 算术运算符…...

RHCSA-使用命令管理文件(3.6)

硬链接与软链接基本操作&#xff1a; 创建软硬连接的命令&#xff1a;ln 硬链接&#xff1a;ln 源文件&#xff08;已经存在的文件&#xff09; 链接文件名&#xff08;新建&#xff09; 软连接&#xff1a;ln -s 源文件&#xff08;已存在的文件&#xff09; 快捷方式文件名…...

socket聊天室--socket的建立

socket聊天室–socket实现 文章目录 socket聊天室--socket实现socket()bind()listen()accept()connect()发送接收read()函数recv()函数write()函数send()函数close()关闭套接字IP 地址格式转换函数socket() #include <sys/types...

Raft图文详解

Raft图文详解 refer to: Raft lecture (Raft user study) - YouTube Raft PDF Raft算法详解 - 知乎 (zhihu.com) 今天来详细介绍一下Raft协议 Raft是来解决公式问题的协议&#xff0c;那么什么是共识呢&#xff1f; 在分布式系统里面&#xff0c;consensus指的是多个节点对…...

春季出游,学会这些功能,让你旅途更舒心

春意盎然&#xff0c;万物复苏&#xff0c;春天正是旅游观光的好时节&#xff0c;相信不少小伙伴已经做好了出游的准备。想拥有好的心情&#xff0c;除了美食美景&#xff0c;好的出游神器也必不可少&#xff0c;好的出游神器能让我们的旅途更舒心&#xff0c;一起来看看是哪些…...

【华为OD机试真题java、python、c++、jsNode】简单的自动曝光【2022 Q4 100分】(100%通过)

代码请进行一定修改后使用,本代码保证100%通过率。本文章提供java、python、c++、jsNode四种代码 题目描述 一个图像有n个像素点,存储在一个长度为n的数组img里,每个像素点的取值范围[0,255]的正整数。 请你给图像每个像素点值加上一个整数k(可以是负数),得到新图newImg…...

react学习笔记-1:创建项目

安装nodejs https://nodejs.org/dist/v18.14.2/node-v18.14.2-x64.msi 修改国内源&#xff1a;npm config set registry https://registry.npm.taobao.org 使用create-react-app脚手架创建项目 安装脚手架 npm install -g create-react-app 全局安装&#xff0c;可以在任意的…...

vulnhub five86-2

总结&#xff1a;sudo -l&#xff0c;抓流量包&#xff0c;搜索引擎。。 目录 下载地址 漏洞分析 信息收集 网站渗透 ​编辑 反弹shell提权 下载地址 Five86-2.zip (Size: 1.7 GB)Download (Mirror): https://download.vulnhub.com/five86/Five86-2.zip使用&#xff1a;下…...

OpenCV入门(四)快速学会OpenCV3画基本图形

OpenCV入门&#xff08;四&#xff09;快速学会OpenCV3画基本图形 1.画点 在OpenCV中&#xff0c;点分为2D平面中的点和3D平面中的点&#xff0c;区别就是3D中点多了一个z坐标。我们首先介绍2D中的点&#xff0c;坐标为整数的点可以直接用(x, y)代替&#xff0c;其中x是横坐标…...

【MAC OS 命令行】Redis的安装、启动和停止。就是如此简单

目录Mac 安装 Redis使用 Homebrew 安装 Redis总结Mac 安装 Redis 使用 Homebrew 安装 Redis 如果没有安装 Homebrew&#xff0c;先安装 Homebrew 执行命令&#xff1a; 方法一、brew 官网的安装脚本 /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homeb…...

Leetecode 661. 图片平滑器

图像平滑器 是大小为 3 x 3 的过滤器&#xff0c;用于对图像的每个单元格平滑处理&#xff0c;平滑处理后单元格的值为该单元格的平均灰度。 每个单元格的 平均灰度 定义为&#xff1a;该单元格自身及其周围的 8 个单元格的平均值&#xff0c;结果需向下取整。&#xff08;即&…...

剑指 Offer II 020. 回文子字符串的个数

题目链接 剑指 Offer II 020. 回文子字符串的个数 mid 题目描述 给定一个字符串 s&#xff0c;请计算这个字符串中有多少个回文子字符串。 具有不同开始位置或结束位置的子串&#xff0c;即使是由相同的字符组成&#xff0c;也会被视作不同的子串。 示例 1&#xff1a; 输入…...

Python实现多键字典

实现背景 在许多场景中&#xff0c;有时需要通过多种信息来获取某个特定的值&#xff0c;而各种编程语言&#xff08;包括Python&#xff09;使用的字典&#xff08;Dict&#xff09;数据结构通常只支持单个键值寻值key-val对&#xff0c;即“一对一”&#xff08;一个键对应一…...

【python socket】实现websocket服务端

一、获取握手信息首先通过如下代码&#xff0c;我们使用socket来获取客户端的握手信息import socketsock socket.socket(socket.AF_INET, socket.SOCK_STREAM) sock.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1) sock.bind(("127.0.0.1", 8002)) sock.li…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...