【C++】二分查找算法:x的平方根

1.题目

2.算法思路

看到题目可能不容易想到二分查找。

这题考察我们对算法的熟练程度。

二分查找的特点:数组具有二段性(不一定有序)。

题目中没有数组,我们可以造一个从0到x的数组,然后利用二分查找找到对应的值即可。

3.代码

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

时间复杂度:O(logn)。

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

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

相关文章

八种单例模式

文章目录 1.单例模式基本介绍1.介绍2.单例模式八种方式 2.饿汉式&#xff08;静态常量&#xff0c;推荐&#xff09;1.基本步骤1.构造器私有化&#xff08;防止new&#xff09;2.类的内部创建对象3.向外暴露一个静态的公共方法 2.代码实现3.优缺点分析 3.饿汉式&#xff08;静态…

如何查看热门GPT应用?

1、登陆chatgpt 2、访问 https://chatgpt.com/gpts 3、在该界面&#xff0c;可以搜索并使用image generator, Write For Me&#xff0c;Language Teature等热门应用。

【Qt 学习笔记】Qt窗口 | 菜单栏 | QMenuBar的使用及说明

博客主页&#xff1a;Duck Bro 博客主页系列专栏&#xff1a;Qt 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ Qt窗口 | 菜单栏 | QMenuBar的使用及说明 文章编号&#xff1a;Qt 学习…

Go微服务: Nacos的搭建和基础API的使用

Nacos 概述 文档&#xff1a;https://nacos.io/docs/latest/what-is-nacos/搭建&#xff1a;https://nacos.io/docs/latest/quickstart/quick-start-docker/有很多种搭建方式&#xff0c;我们这里使用 docker 来搭建 Nacos 的搭建 这里&#xff0c;我们选择单机模式&#xf…

Redis可视化工具:Another Redis Desktop Manager下载安装使用

1.Github下载 github下载地址&#xff1a; Releases qishibo/AnotherRedisDesktopManager GitHub 2. 安装 直接双击exe文件进行安装 3. 连接Redis服务 先启动Redis服务&#xff0c;具体启动过程可参考&#xff1a; Windows安装并启动Redis服务端&#xff08;zip包&#xff09…

从程序被SQL注入来MyBatis 再谈 #{} 与 ${} 的区别

缘由 最近在的一个项目上面&#xff0c;发现有人在给我搞 SQL 注入&#xff0c;我真的想说我那么点资源测试用的阿里云服务器&#xff0c;个人估计哈&#xff0c;估计能抗住他的请求。狗头.png 系统上面的截图 数据库截图 说句实在的&#xff0c;看到这个之后我立马就是在…

Nginx文件解析漏洞复现:CVE-2013-4547

漏洞原理 CVE-2013-4547漏洞是由于非法字符空格和截止符导致Nginx在解析URL时的有限状态机混乱&#xff0c;导致攻击者可以通过一个非编码空格绕过后缀名限制。假设服务器中存在文件1. jpg&#xff0c;则可以通过改包访问让服务器认为访问的为PHP文件。 漏洞复现 开启靶场 …

【数据结构】快速排序详解!

文章目录 1. 快速排序的非递归版本2. 快速排序2.1 hoare 版本一2.2 挖坑法 &#x1f427;版本二2.3 前后指针 版本三2.4 调用以上的三个版本的快排 3. 快速排序的优化 1. 快速排序的非递归版本 &#x1f192;&#x1f427;关键思路&#xff1a; &#x1f34e;① 参数中的begin…

呆马科技----构建智能可信的踏勘云平台

近年来&#xff0c;随着信息技术的快速发展&#xff0c;各个行业都在积极探索信息化的路径&#xff0c;以提升工作效率和服务质量。智慧踏勘云平台是基于区块链和大数据技术构建的全流程智慧可信踏勘解决平台。平台集远程视频、数据显示、工作调度、过程记录为一体&#xff0c;…

嵌入式进阶——舵机控制PWM

&#x1f3ac; 秋野酱&#xff1a;《个人主页》 &#x1f525; 个人专栏:《Java专栏》《Python专栏》 ⛺️心若有所向往,何惧道阻且长 文章目录 舵机信号线代码示例初始化PWM初始化UART打印日志初始化外部中断Extimain函数 舵机最早用于船舶上实现转向功能,由于可以通过程序连…

Spring从零开始学使用系列(四)之@PostConstruct和@PreDestroy注解的使用

如果各位老爷觉得可以&#xff0c;请点赞收藏评论&#xff0c;谢谢啦&#xff01;&#xff01; 文章中涉及到的图片均由AI生成 公众号在最下方&#xff01;&#xff01;&#xff01; 目录 1. 介绍 1.1 PostConstruct概述 1.2 PreDestroy概述 2. 基本用法 2.1 注册CommonAnn…

JS根据所选ID数组在源数据中取出对象

let selectIds [1, 3] // 选中id数组let allData [{ id: 1, name: 123 },{ id: 2, name: 234 },{ id: 3, name: 345 },{ id: 4, name: 456 },] // 源数据let newList [] // 最终数据selectIds.map((i) > {allData.filter((item) > {item.id i && newList.pus…

MyBatis复习笔记

3.Mybatis复习 3.1 xml配置 properties&#xff1a;加载配置文件 settings&#xff1a;设置驼峰映射 <settings><setting name"mapUnderscoreToCamelCase" value"true"/> </settings>typeAliases&#xff1a;类型别名设置 #这样在映射…

力扣刷题---LCS 02. 完成一半题目【简单】

题目描述 有 N 位扣友参加了微软与力扣举办了「以扣会友」线下活动。主办方提供了 2*N 道题目&#xff0c;整型数组 questions 中每个数字对应了每道题目所涉及的知识点类型。 若每位扣友选择不同的一题&#xff0c;请返回被选的 N 道题目至少包含多少种知识点类型。 示例 1&…

MySQL--InnoDB体系结构

目录 一、物理存储结构 二、表空间 1.数据表空间介绍 2.数据表空间迁移 3.共享表空间 4.临时表空间 5.undo表空间 三、InnoDB内存结构 1.innodb_buffer_pool 2.innodb_log_buffer 四、InnoDB 8.0结构图例 五、InnoDB重要参数 1.redo log刷新磁盘策略 2.刷盘方式&…

自然资源-各级国土空间总体规划的审查要点及流程总结

自然资源-各级国土空间总体规划的审查要点及流程总结 国土空间规划是对一定区域国土空间开发保护在空间和时间上作出的安排&#xff0c;包括总体规划、详细规划和相关专项规划。 国土空间规划管理是国土空间规划中重要的一环。中共中央、国务院发布《关于建立国土空间规划体系…

京东应届生公司内网说了一句‘什么时候被pdd收购‘,结果惨遭辞退

京东应届生公司内网说了一句’什么时候被pdd收购’&#xff0c;结果惨遭公司开除 这个事最近在圈子讨论比较多 前二天&#xff0c;有一个上海交大毕业的应届生&#xff0c;在京东实习了9个月&#xff0c;好不容易转正12天后&#xff0c;只因在内网说了一句话&#xff0c;就被…

释放Mac潜能,选择Magic Disk Cleaner for Mac

想要让Mac运行更加流畅、性能更加出色吗&#xff1f;那就选择Magic Disk Cleaner for Mac吧&#xff01; Magic Disk Cleaner for Mac v2.7.7激活版下载 这款软件是Mac用户的得力助手&#xff0c;它拥有强大的扫描和清理功能&#xff0c;能够迅速找出并删除硬盘上的无用文件和垃…

Linux系统命令traceroute详解(语法、选项、原理和实例)

目录 一、traceroute概述 二、语法 1、基本语法 2、命令选项 三、帮助信息 四、示例 1. 使用默认模式&#xff08;ICMP Echo&#xff09;追踪到目标主机 2. 使用UDP模式&#xff08;需要root权限&#xff09;追踪到目标主机 3. 不解析IP地址为主机名&#xff0c;直接显…

前端已死? Bootstrap--CSS组件

目录 Bootstrap 下载 Bootstrap--全局CSS样式 栅格系统 栅格参数 正常显示 实例 代码演示: 排版 代码演示 表格 代码演示 表单 代码演示 等等...(文档很清晰了) Bootstrap--组件 结合演示:(页面) Bootstrap Bootstrap v3 中文文档 Bootstrap 是最受欢迎的 HT…