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

LeetCode | 数组 | 二分查找 | 35.搜索插入位置【C++】

题目链接

题目描述

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 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

分析思路

  • 前提有序数组+数组中无重复元素(一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的)
  • 确认方法:二分查找法
  • 注:二分法中关于区间的定义一般为两种——“左闭右闭[left, right]” 或 “左闭右开[left, right)”

代码实现

实现一:左闭右闭

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;  // 左闭右闭while (left <= right){  // 当left==right,区间[left, right]依然有效,所以用<=int middle = left + ((right - left) / 2);  // 防止溢出if (nums[middle] > target){ // target在左区间 [left, middle-1]right = middle - 1;} else if (nums[middle] < target){ // target在右区间 [middle+1, right]left = middle + 1;} else { // nums[middle] == targetreturn middle; // 找到目标值,直接返回下标}}// 1.目标值在数组所有元素之前 [0, -1]// 2.目标值插入数组中的位置 [left, right]// 3.目标值在数组所有元素之后 [nums.size(), nums.size()-1]return right + 1;// return left;}
};

实现二:左闭右开

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0;int right = nums.size();  // 左闭右开while (left < right){  // 当left==right,区间[left, right)无效int middle = left + ((right - left) / 2);  // 防止溢出// int middle = left + ((right - left) >> 1); // >>按位右移运算符,等同于变量除以2if (nums[middle] > target){ // target在左区间 [left, middle)right = middle;} else if (nums[middle] < target){ // target在右区间 [middle+1, right)left = middle + 1;} else { // nums[middle] == targetreturn middle; // 找到目标值,直接返回下标}}// 1.目标值在数组所有元素之前 [0, 0)// 2.目标值插入数组中的位置 [left, right)// 3.目标值在数组所有元素之后 [nums.size(), nums.size() )return right;// return left;}
};

参考来源:代码随想录 

补充:位移运算符为何能将数据乘以或除以 2^{n} ?

按位右移运算符(>>)将变量除以2^{n};按位左移运算符(<<)将变量乘以2^{n}

例如:

变量num的值为16,其二进制表示为10000。将num右移1位,结果为01000,即8,这相当于将其减半;将num右移两位,变成了00100,即4,相当于计算num的1/4。向左移1位时结果为100000,即32,向左移两位的结果为1000000,即64,相当于计算num的2倍和4倍。

相关文章:

LeetCode | 数组 | 二分查找 | 35.搜索插入位置【C++】

题目链接 题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums [1,3,5,6], target 5 输出…...

Linux 给网卡配置ip

ip addr | grep eth9 ifconfig eth9 10.0.0.2 netmask 255.255.255.0 up...

【C语言】翻译环境与运行环境

一、前言 在我们学习C语言的时候&#xff0c;第一个接触的程序就是&#xff1a;在屏幕上打印” hello word! “&#xff0c;可当时的我们却未去深入的理解与感悟&#xff0c;一个程序代码是如何运行的&#xff1b;而这一期的博客&#xff0c;则是带着我们&#xff0c;通过C代码…...

ubuntu20.04执行sudo apt-get update失败的解决方法

参考&#xff1a;执行sudo apt-get update失败的解决方案 1、换源型错误 &#xff08;1&#xff09;编辑/etc/apt/sources.list文件 在命令行中输入&#xff1a; sudo vim /etc/apt/sources.list 或者 sudo gedit /etc/apt/sources.list 推荐使用后者 &#xff08;2&#xf…...

接口调用成功后端却一直返回404

vuespringboot 我在vue.config.js中配置了向后端的反向代理 然后使用了axios向后端发送post请求 可以看到可以接收到前端传来的值 但是前端控制台却报了 “xhr.js:245POST http://localhost:7777/api/login 404 (Not Found)” 最后询问我那智慧的堂哥... ... 解决办法是把C…...

【Vmware】 debian 12 安装教程

1.前提说明 VMware 17.5.1 (自行安装)&#xff0c;参考Debian 12maven 3.8.7git 2.39.2jdk 1.8 / 11 / 17 1.1.Debian 下载 访问(https://www.debian.org/download) 下载 Debian 这是 Debian 12&#xff0c;代号为 bookworm&#xff0c;网络安装&#xff0c;用于 64 位 PC&a…...

YooAssets 使用相关

## 使用 YooAssets 动态加载原生文件时候 > 原生文件&#xff1a;txt&#xff1b;json&#xff1b;等需要直接保存文件内string字符的文件 需要将打包方式设置成为&#xff0c;PackRawFile 并且加载时候使用 API &#xff1a; YooAssets.LoadRawFileSync()YooAssets.LoadRa…...

精准扶贫管理系统|基于Springboot的精准扶贫管理系统设计与实现(源码+数据库+文档)

精准扶贫管理系统目录 目录 基于Springboot的精准扶贫管理系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、管理员模块的实现 &#xff08;1&#xff09;用户信息管理 &#xff08;2&#xff09;贫困户信息管理 &#xff08;3&#xff09;新闻类型管理 &a…...

Flutter与iOS和Android原生页面交互

一、Flutter 与原生页面交互的重要性和应用场景 Flutter 是一个由 Google 开发的开源框架&#xff0c;用于创建跨平台的移动、Web 和桌面应用程序。Flutter 允许开发者使用一套代码库为 Android 和 iOS 等平台构建美观、高性能的应用程序。然而&#xff0c;尽管 Flutter 提供了…...

Chrome安装Vue插件vue-devtools

直接通过网站&#xff1a; Home | Vue Devtools (vuejs.org) chrome扩展商城中搜索&#xff1a;Vue.js devtools 参考下面edge扩展商城的图&#xff0c;两者流程相近...

内存和网卡压力测试

1.内存压力测试 1.1测试目的 内存压力测试的目的是评估开发板中的内存子系统性能和稳定性&#xff0c;以确保它能够满足特定的应用需求。开发板通常用于嵌入式系统、物联网设备、嵌入式智能家居等场景&#xff0c;这些场景对内存的要求通常比较高。 其内存压力测试的主要目的…...

法律行业案例法模型出现,OPenAI公布与法律AI公司Harvey合作案例

Harvey与OpenAl合作&#xff0c;为法律专业人士构建了一个定制训练的案例法模型。该模型是具有复杂推理广泛领域知识以及超越单一模型调用能力的任务的AI系统&#xff0c;如起草法律文件、回答复杂诉讼场景问题以及识别数百份合同之间的重大差异。 Harvey公司由具有反垄断和证…...

详解Qt网络编程

Qt的网络编程能力非常强大&#xff0c;它提供了从底层socket API到高层HTTP、FTP等协议处理的完整解决方案。下面将简要介绍Qt中网络编程的核心类及其功能&#xff0c;并给出一些基本的使用示例。 核心网络类&#xff1a; QTcpSocket 和 QTcpServer QTcpSocket 是用于TCP通信的…...

docker版Elasticsearch安装,ik分词器安装,用户名密码配置,kibana安装

1、安装es和ik分词器 创建映射目录并赋予权限&#xff1a; mkdir -p /docker_data/elasticsearch/conf mkdir -p /docker_data/elasticsearch/data mkdir -p /docker_data/elasticsearch/plugins chmod -R 777 /docker_data/elasticsearch编写配置文件&#xff1a; vi /dock…...

Python中的Requests库:HTTP请求的简单之道

目录 一、安装Requests库 二、发送请求 2.1 GET请求 2.2 POST请求 2.3 其他HTTP方法 三、处理响应 3.1 状态码 3.2 响应内容 3.3 自定义请求头 3.4 更多响应对象属性和方法 四、错误处理 五、高级请求 5.1 会话对象 5.2 SSL证书验证 5.3 设置代理 Http/Https代…...

[RK3566-Android11] 关于 a2dpsink -蓝牙支持接收播放/无PIN码连接

问题描述 1.蓝牙支持接收播放 2.蓝牙支持无PIN码连接&#xff08;不需要弹出pin配对码请求弹窗&#xff09; 3.蓝牙支持播放歌曲信息并应用层获取 解决方案&#xff1a; 1.a2dpsink-蓝牙需要支持接收播放补丁 1、device/rockchip/common/overlay/overlay/packages/apps/Blue…...

玩机进阶教程-----高通9008线刷XML脚本修改备份 檫除的操作步骤解析

在高通9008官方固件中我们可以看到刷写需要的脚本rawprogram0.xml和辅助脚本patch0.xml&#xff0c;脚本的作用在于将固件内各个分区对应写入手机内。根据分区地址段。然后判断脚本中那些分区不写入。以下步骤将分析emmc字库为例来讲解如何将默认刷入脚本修改为备份 檫除脚本。…...

前端路径问题总结

1.相对路径 不以/开头 以当前资源的所在路径为出发点去找目标资源 语法: ./表示当前资源的路径 ../表示当前资源的上一层路径 缺点:不同位置,相对路径写法不同2.绝对路径 以固定的路径作为出发点作为目标资源,和当前资源所在路径没关系 语法:以/开头,不同的项目中,固定的路径…...

YOLOv8改进 | 低照度检测 | 2024最新改进CPA-Enhancer链式思考网络(适用低照度、图像去雾、雨天、雪天)

一、本文介绍 本文给大家带来的2024.3月份最新改进机制,由CPA-Enhancer: Chain-of-Thought Prompted Adaptive Enhancer for Object Detection under Unknown Degradations论文提出的CPA-Enhancer链式思考网络,CPA-Enhancer通过引入链式思考提示机制,实现了对未知退化条件下…...

python的pip如何升级

升级pip的方法如下&#xff1a; 打开命令行工具。在Windows系统中&#xff0c;可以通过按下WinR键&#xff0c;然后输入"cmd"来打开命令提示符&#xff1b;在Mac或Linux系统中&#xff0c;可以直接打开终端。检查当前pip版本。在终端或命令行中输入以下命令&#…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献

Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译&#xff1a; ### 胃肠道癌症的发病率呈上升趋势&#xff0c;且有年轻化倾向&#xff08;Bray等人&#xff0c;2018&#x…...

ubuntu中安装conda的后遗症

缘由: 在编译rk3588的sdk时&#xff0c;遇到编译buildroot失败&#xff0c;提示如下&#xff1a; 提示缺失expect&#xff0c;但是实测相关工具是在的&#xff0c;如下显示&#xff1a; 然后查找借助各个ai工具&#xff0c;重新安装相关的工具&#xff0c;依然无解。 解决&am…...

P10909 [蓝桥杯 2024 国 B] 立定跳远

# P10909 [蓝桥杯 2024 国 B] 立定跳远 ## 题目描述 在运动会上&#xff0c;小明从数轴的原点开始向正方向立定跳远。项目设置了 $n$ 个检查点 $a_1, a_2, \cdots , a_n$ 且 $a_i \ge a_{i−1} > 0$。小明必须先后跳跃到每个检查点上且只能跳跃到检查点上。同时&#xff0…...