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

这个题是经典的二分算法,但是略有改进。

二分查找(Binary Search)是一种在有序数组中查找特定元素的高效算法。它的基本思想是将目标值与数组中间的元素进行比较,如果目标值小于中间元素,则在数组的左半部分继续查找,否则在右半部分查找,不断缩小搜索范围,直到找到目标值或确定目标值不存在为止。

二分查找也叫折半查找,比如在一个有序的数组里面找到目标值,它是一种查询效率比较高的算法,时间复杂度O(logn)。比如在下面数组找到 6.首先在定位到两侧,也就是最大值和最小值。并找到中间和目标值比较。

中间值是 5,比目标值更小,就要缩小范围,中间值作为最小值,在中间值右边的区域再找到中间值和目标值比较。

以此类推,一直缩小范围,直到找到目标值,或者搜索完数据。

本题就是在二分的基础上进行改进,本质和折半插入排序一致,在最后返回时,要返回low或者high+1,即要插入的位置。

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/227316.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

大开眼界,速看!Solid Edge各版本安装指南

下载链接 https://pan.baidu.com/s/1g3QEGoLsjD7JaudZUOW96Q?pwd0531 1.鼠标右击【Solid Edge2024(64bit)】压缩包&#xff08;win11及以上系统需先点击“显示更多选项”&#xff09;【解压到 Solid Edge2024(64bit)】。 2.打开解压后的文件夹&#xff0c;双击打开【Setup】文…

【前端技术】LocalForage数据存储

✨专栏介绍 在当今数字化时代&#xff0c;Web应用程序已经成为了人们生活和工作中不可或缺的一部分。而要构建出令人印象深刻且功能强大的Web应用程序&#xff0c;就需要掌握一系列前端技术。前端技术涵盖了HTML、CSS和JavaScript等核心技术&#xff0c;以及各种框架、库和工具…

算法训练营Day26

#Java #全排列 #回溯 开源学习资料 Feeling and experiences&#xff1a; 递增子序列&#xff1a;力扣题目链接 给你一个整数数组 nums &#xff0c;找出并返回所有该数组中不同的递增子序列&#xff0c;递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 数组…

《PCI Express体系结构导读》随记 —— 第I篇 第1章 PCI总线的基本知识(18)

接前一篇文章&#xff1a;《PCI Express体系结构导读》随记 —— 第I篇 第1章 PCI总线的基本知识&#xff08;17&#xff09; 1.4 PCI总线的中断机制 1.4.2 中断信号与PCI总线的连接关系 在PCI总线中&#xff0c;INTx信号属于边带信号。所谓边带信号是指这些信号在PCI总线环境…

深入了解云原生:定义与特征解析

文章目录 一、云原生概述1.1 什么是云原生1.2 云原生组成要素1.3 补充资料 二、云原生的目标2.1 云原生关键目标2.2 云原生特性 三、云原生应用 VS 传统单体应用参考资料 一、云原生概述 1.1 什么是云原生 (1)云原生定义 云原生(Cloud Native) 是一种软件架构和开发方法论&a…

二叉树顺序结构与堆的概念及性质(c语言实现堆)

上次介绍了树&#xff0c;二叉树的基本概念结构及性质&#xff1a;二叉树数据结构&#xff1a;深入了解二叉树的概念、特性与结构 今天带来的是&#xff1a;二叉树顺序结构与堆的概念及性质&#xff0c;还会用c语言来实现堆 文章目录 1. 二叉树的顺序结构2.堆的概念和结构3.堆…

Vue : 监视属性

目录 一个案例 监听属性 handler immediate vm.$watch(xxx) 深度监视 监视的简写 computed和watch之间的区别 一个案例 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport"…

使用TLS/SSL Pinning保护安卓应用程序

使用TLS/SSL Pinning保护安卓应用程序 在现代术语中&#xff0c;“SSL”&#xff08;安全套接层&#xff09;通常指的是“TLS”&#xff08;传输层安全&#xff09;。虽然 SSL 和 TLS 不是同一个东西&#xff0c;但 TLS 是 SSL 的改进和更安全的版本&#xff0c;并且在实践中已…

前后端分离nodejs+vue+ElementUi网上订餐系统69b9

课题主要分为两大模块&#xff1a;即管理员模块和用户模块&#xff0c;主要功能包括个人中心、用户管理、菜品类型管理、菜品信息管理、留言反馈、在线交流、系统管理、订单管理等&#xff1b; 运行软件:vscode 前端nodejsvueElementUi 语言 node.js 框架&#xff1a;Express/k…

超详细YOLOv8姿态检测全程概述:环境、训练、验证与预测详解

目录 yolov8导航 YOLOv8&#xff08;附带各种任务详细说明链接&#xff09; 搭建环境说明 不同版本模型性能对比 不同版本对比 参数解释 模型解释 训练 训练示意代码 训练数据与.yaml配置方法 .yaml配置 数据集路径 标签数据说明 训练参数说明 训练过程示意及输出…

集群部署篇--Redis 主从模式

文章目录 前言Redis 主从部署&#xff1a;1.1 主从架构 介绍&#xff1a;1.2 主从架构 实现&#xff1a;1.2.1 redis 安装&#xff1a; 1.3 主从架构优缺点&#xff1a;1.4 故障转移&#xff1a; 总结 前言 显然在线上环境中 Redis 服务不能以单机的方式运行&#xff0c;必须有…

PostgreSQL 作为向量数据库:入门和扩展

PostgreSQL 拥有丰富的扩展和解决方案生态系统&#xff0c;使我们能够将该数据库用于通用人工智能应用程序。本指南将引导您完成使用 PostgreSQL 作为向量数据库构建生成式 AI 应用程序所需的步骤。 我们将从pgvector 扩展开始&#xff0c;它使 Postgres 具有特定于向量数据库…

【C++】开源:fast-cpp-csv-parser数据解析库配置使用

&#x1f60f;★,:.☆(&#xffe3;▽&#xffe3;)/$:.★ &#x1f60f; 这篇文章主要介绍fast-cpp-csv-parser数据解析库配置使用。 无专精则不能成&#xff0c;无涉猎则不能通。——梁启超 欢迎来到我的博客&#xff0c;一起学习&#xff0c;共同进步。 喜欢的朋友可以关注一…

C/C++学习笔记十三 C++中的重载运算符

1、什么是运算符重载&#xff1f; 运算符重载是 C 中的一项功能&#xff0c;使运算符&#xff08;例如 、- 等&#xff09;能够处理用户定义的数据类型。这种机制称为编译时多态性&#xff0c;并提供了为不同数据类型定制运算符行为的优点。 例如&#xff0c;我们可以重载“”运…

查看IOS游戏FPS

摘要 本篇技术博客将介绍如何使用克魔助手工具来查看iOS游戏的帧率&#xff08;FPS&#xff09;。通过克魔助手&#xff0c;开发者可以轻松监测游戏性能&#xff0c;以提升用户体验和游戏质量。 引言 在iOS游戏开发过程中&#xff0c;了解游戏的帧率对于优化游戏性能至关重要…

沙特电子签证照片尺寸要求及手机自拍制作方法介绍

Hey小伙伴们&#xff0c;准备去沙特阿拉伯旅行的朋友们注意啦&#xff01;沙特驻华大使馆对签证所需照片是有要求的&#xff0c;今天我要分享给大家的是关于沙特签证照片的尺寸和拍摄要求&#xff0c;让你的签证申请过程更加顺利哦&#xff01;此外&#xff0c;也教大家一种在家…

[Angular] 笔记 20:NgContent

chatgpt: 在Angular中&#xff0c;NgContent是用于内容投影&#xff08;Content Projection&#xff09;的一个重要概念。它允许你在一个组件中插入内容&#xff0c;并将这些内容投影到另一个组件中。 当你在一个组件中使用<ng-content></ng-content>标签时&…

redis 从0到1完整学习 (七):ZipList 数据结构

文章目录 1. 引言2. redis 源码下载3. zipList 数据结构3.1 整体3.2 entry 数据结构分析3.3 连锁更新 4. 参考 1. 引言 前情提要&#xff1a; 《redis 从0到1完整学习 &#xff08;一&#xff09;&#xff1a;安装&初识 redis》 《redis 从0到1完整学习 &#xff08;二&am…

Elasticsearch 查询命令执行时,如何通过词项索引、词项字典、倒排表定位文档逻辑介绍

这里不涉及到源码&#xff0c;只是根据网上的一些文章总结一下&#xff0c;目前不需要细究&#xff0c;只需要知道大概就好&#xff0c;除非你的工作是二次开发ES 一、​Term Index(词项索引)1、FSM&#xff08;Finite State Machine&#xff09;有限状态机2、FSA&#xff08;F…

海云安亮相2023北京国际金融安全论坛,助力金融企业数字化转型降本增效

近日&#xff0c;2023北京国际金融安全论坛暨金融科技标准认证生态大会在北京金融安全产业园成功举办。深圳海云安网络安全技术有限公司&#xff08;以下简称“海云安”&#xff09;受邀参展亮相此次大会。海云安作为国内领先的金融科技服务商&#xff0c;展示了开发安全系列产…