二分搜索(三)x的平方根

69. x 的平方根 

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

请必须使用时间复杂度为 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开始依次遍历,当i平方刚好大于或等于目标值时返回

class Solution {
public:int mySqrt(int x) {for(long long i = 1; i <= x; i++){if(i * i == x)return (int)i;else if(i * i > x)return (int)i-1;}return 0;}
};

二分优化

 结果只会出现在小于mid平方位置,所以在 <= 目标值进行更新ret即可

class Solution {
public:int mySqrt(int x) {int left = 0, right = x, ret = -1;while(left <= right){int mid = left + (right - left)/2;if((long long) mid * mid <= x){ret = mid;left = mid + 1;}elseright = mid - 1;}return ret;}
};

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

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

相关文章

AI开发-数据可视化库-Seaborn

1 需求 概述 Seaborn 是一个基于 Python 的数据可视化库&#xff0c;它建立在 Matplotlib 之上。其主要目的是使数据可视化更加美观、方便和高效。它提供了高层次的接口和各种美观的默认主题&#xff0c;能够帮助用户快速创建出具有吸引力的统计图表&#xff0c;用于数据分析和…

使用docker-compose部署搜索引擎ElasticSearch6.8.10

背景 Elasticsearch 是一个开源的分布式搜索和分析引擎&#xff0c;基于 Apache Lucene 构建。它被广泛用于实时数据搜索、日志分析、全文检索等应用场景。 Elasticsearch 支持高效的全文搜索&#xff0c;并提供了强大的聚合功能&#xff0c;可以处理大规模的数据集并进行快速…

LeetCode—74. 搜索二维矩阵(中等)

仅供个人学习使用 题目描述&#xff1a; 给你一个满足下述两条属性的 m x n 整数矩阵&#xff1a; 每行中的整数从左到右按非严格递增顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target &#xff0c;如果 target 在矩阵中&#xff0c;返回 true…

Cento7 紧急模式无法正常启动,修复home挂载问题

Centos 7 开机失败进入紧急模式[emergency mode]&#xff0c;解决方案。 通过journalctl -xb查看启动日志&#xff0c;定位发现/home目录无法正常挂载。 退出启动日志检查&#xff0c;进行修复。 进行问题修复 # 修复挂载问题 mkdir /home mount /dev/mapper/centos-home /ho…

Matlab mex- setup报错—错误使用 mex,未检测到支持的编译器...

错误日志&#xff1a; 在使用mex编译时报错提示&#xff1a;错误使用 mex&#xff0c;未检测到支持的编译器。您可以安装免费提供的 MinGW-w64 C/C 编译器&#xff1b;请参阅安装 MinGW-w64 编译器。有关更多选项&#xff0c;请访问https://www.mathworks.com/support/compile…

【C语言】二叉树(BinaryTree)的创建、3种递归遍历、3种非递归遍历、结点度的实现

代码主要实现了以下功能&#xff1a; 二叉树相关数据结构定义 定义了二叉树节点结构体 BiTNode&#xff0c;包含节点数据值&#xff08;字符类型&#xff09;以及指向左右子树的指针。 定义了顺序栈结构体 SqStack&#xff0c;用于存储二叉树节点指针&#xff0c;实现非递归遍历…

Android -- 简易音乐播放器

Android – 简易音乐播放器 播放器功能&#xff1a;* 1. 播放模式&#xff1a;单曲、列表循环、列表随机&#xff1b;* 2. 后台播放&#xff08;单例模式&#xff09;&#xff1b;* 3. 多位置同步状态回调&#xff1b;处理模块&#xff1a;* 1. 提取文件信息&#xff1a;音频文…

Python语法基础(四)

&#x1f308;个人主页&#xff1a;羽晨同学 &#x1f4ab;个人格言:“成为自己未来的主人~” 高阶函数之map 高阶函数就是说&#xff0c;A函数作为B函数的参数&#xff0c;B函数就是高阶函数 map&#xff1a;映射 map(func,iterable) 这个是map的基本语法&#xff0c;…

大模型时代的人工智能基础与实践——基于OmniForce的应用开发教程

《大模型时代的人工智能基础与实践——基于 OmniForce 的应用开发教程》由京东探索研究院及京东教育联袂撰写&#xff0c;图文并茂地介绍传统人工智能和新一代人工智能&#xff08;基于大模型的通用人工智能技术&#xff09;&#xff0c;展示人工智能广阔的应用场景。同时&…

ESP8266 (ESP-01S)烧录固件 和 了解与单片机通信必需的AT指令

ESP8266&#xff08;ESP-01s&#xff09;烧录固件 工具&#xff1a; 需要安装的原装出厂固件库&#xff1a; ESP8266 --接线-- VCC 3.3&#xff08;外接开发板&#xff09; GND GND&#xff08;外接开发板&#xff09; IO0 GND&#xff08;外接…

【操作文档】mysql分区操作步骤.docx

1、建立分区表 执行 tb_intercept_notice表-重建-添加分区.sql 文件&#xff1b; DROP TABLE IF EXISTS tb_intercept_notice_20241101_new; CREATE TABLE tb_intercept_notice_20241101_new (id char(32) NOT NULL COMMENT id,number varchar(30) NOT NULL COMMENT 号码,cre…

S4 UPA of AA :新资产会计概览

通用并行会计&#xff08;Universal Parallel Accounting&#xff09;可以支持每个独立的分类账与其他模块集成&#xff0c;UPA主要是为了支持平行评估、多货币类型、财务合并、多准则财务报告的复杂业务需求 在ML层面UPA允许根据不同的分类账规则对物料进行评估&#xff0c;并…

ScribblePrompt 医学图像分割工具,三种标注方式助力图像处理

ScribblePrompt 的主要目标是简化医学图像的分割过程&#xff0c;这在肿瘤检测、器官轮廓描绘等应用中至关重要。相比依赖大量人工标注数据&#xff0c;该工具允许用户通过少量输入&#xff08;例如简单的涂鸦或点位&#xff09;来引导模型优化分割结果。这种方式减少了医学专家…

jdk各个版本介绍

Java Development Kit&#xff08;JDK&#xff09;是Java平台的核心组件&#xff0c;它包含了Java编程语言、Java虚拟机&#xff08;JVM&#xff09;、Java类库以及用于编译、调试和运行Java应用程序的工具。 JDK 1.0-1.4&#xff08;经典时代&#xff09; • JDK 1.0&#xff…

【Python爬虫五十个小案例】爬取猫眼电影Top100

博客主页&#xff1a;小馒头学python 本文专栏: Python爬虫五十个小案例 专栏简介&#xff1a;分享五十个Python爬虫小案例 &#x1f40d;引言 猫眼电影是国内知名的电影票务与资讯平台&#xff0c;其中Top100榜单是影迷和电影产业观察者关注的重点。通过爬取猫眼电影Top10…

Doge东哥wordpress主题

Doge东哥wordpress主题是一款专为中小型企业设计的WordPress外贸网站模板&#xff0c;它以其现代、专业且用户友好的界面&#xff0c;为企业提供了一个展示产品和服务的理想平台。以下是对该模板的详细描述&#xff1a; 首页设计概览 首页的设计简洁而不失大气&#xff0c;顶…

【力扣】541.反转字符串2

问题描述 思路解析 每当字符达到2*k的时候&#xff0c;判断&#xff0c;同时若剩余字符>k,只对前k个进行判断&#xff08;这是重点&#xff09;因为字符串是不可变变量&#xff0c;所以将其转化为字符串数组&#xff0c;最后才将结果重新转变为字符串 字符串->字符数组 …

C++练级计划-> 《IO流》iostream fstream sstream详解

如果是想全部过一遍就看完&#xff0c;如果想具体的了解某一个请点目录。因为有三种流的使用可能内容多 目录 流是什么&#xff1f; CIO流&#xff08;iostream&#xff09; io流的注意事项 cin和cout为什么能直接识别出类型和数据 fstream fstream的使用方法&#xff…

EDA软件研发的DevOps平台

1&#xff1a;什么是DevOps DevOps是十几年前&#xff0c;在互联网比较火的词&#xff0c;实际上就是ci/cd平台的另外一种说法&#xff0c;核心是说打破研发&#xff0c;测试&#xff0c;运维的边界&#xff0c;能够将整个产品开发的流程快速循环起来&#xff0c;随时可发版&a…

自动化是语法,智能化是语义与语用

自动化与智能化可以从语言学的角度来进行类比和探讨。 1. 自动化是语法 自动化可以类比为“语法”的部分&#xff0c;因为它关注的是操作过程的规则、结构和执行方式。语法是语言中关于词汇、句子结构和规则的系统&#xff0c;它提供了语言运作的框架和规范。类似地&#xff0c…