二分搜索小结-x的平方根

2024-05-20 19:38
文章标签 搜索 二分 小结 平方根

本文主要是介绍二分搜索小结-x的平方根,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

二分查找法作为一种常见的查找方法,将原本是线性时间提升到了对数时间范围,大大缩短了搜索时间,具有很大的应用场景,而在LeetCode中,要运用二分搜索法来解的题目也有很多,但是实际上二分查找法的查找目标有很多种,而且在细节写法也有一些变化。

第一类: 需查找和目标值完全相等的数

这是最简单的一类,也是我们最开始学二分查找法需要解决的问题,比如我们有数组[2, 4, 5, 6, 9],target = 6,那么我们可以写出二分查找法的代码如下:

def find(nums,target):l, r = 0, len(nums)-1while l < r:mid = l + (r-l)//2if nums[mid] == target:return midelif nums[mid] < target:l = mid + 1else:r  = mid - 1return r
def main():nums = [1,2,4,6,8]target=8print(find(nums,target))
main()

第二类: 查找第一个不小于目标值的数,可变形为查找最后一个小于目标值的数

这是比较常见的一类,因为我们要查找的目标值不一定会在数组中出现,也有可能是跟目标值相等的数在数组中并不唯一,而是有多个,那么这种情况下nums[mid] == target这条判断语句就没有必要存在。比如在数组[2, 4, 5, 6, 9]中查找数字3,就会返回数字4的位置;在数组[0, 1, 1, 1, 1]中查找数字1,就会返回第一个数字1的位置。我们可以使用如下代码:

def find(nums,target):l, r = 0, len(nums)-1while l < r:mid = l + (r-l)//2if nums[mid] == target:return midelif nums[mid] < target:l = mid + 1else:r  = middef main():nums = [0,1,1,1,1]target=1print(find(nums,target))
main()

69.实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数,小数部分将被舍去。

class Solution:def mySqrt(self, x: int) -> int:if x == 0:return 0if x == 1:return 1l, r = 0, x - 1while l <= r:mid = l + (r-l)//2if mid * mid <= x and (mid+1)*(mid+1) > x:return midelif mid*mid > x:r = mid-1else:l = mid+1

这篇关于二分搜索小结-x的平方根的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

C#中Guid类使用小结

《C#中Guid类使用小结》本文主要介绍了C#中Guid类用于生成和操作128位的唯一标识符,用于数据库主键及分布式系统,支持通过NewGuid、Parse等方法生成,感兴趣的可以了解一下... 目录前言一、什么是 Guid二、生成 Guid1. 使用 Guid.NewGuid() 方法2. 从字符串创建

Redis分片集群、数据读写规则问题小结

《Redis分片集群、数据读写规则问题小结》本文介绍了Redis分片集群的原理,通过数据分片和哈希槽机制解决单机内存限制与写瓶颈问题,实现分布式存储和高并发处理,但存在通信开销大、维护复杂及对事务支持... 目录一、分片集群解android决的问题二、分片集群图解 分片集群特征如何解决的上述问题?(与哨兵模

SpringBoot中使用Flux实现流式返回的方法小结

《SpringBoot中使用Flux实现流式返回的方法小结》文章介绍流式返回(StreamingResponse)在SpringBoot中通过Flux实现,优势包括提升用户体验、降低内存消耗、支持长连... 目录背景流式返回的核心概念与优势1. 提升用户体验2. 降低内存消耗3. 支持长连接与实时通信在Sp

Python打印对象所有属性和值的方法小结

《Python打印对象所有属性和值的方法小结》在Python开发过程中,调试代码时经常需要查看对象的当前状态,也就是对象的所有属性和对应的值,然而,Python并没有像PHP的print_r那样直接提... 目录python中打印对象所有属性和值的方法实现步骤1. 使用vars()和pprint()2. 使

HTML5 getUserMedia API网页录音实现指南示例小结

《HTML5getUserMediaAPI网页录音实现指南示例小结》本教程将指导你如何利用这一API,结合WebAudioAPI,实现网页录音功能,从获取音频流到处理和保存录音,整个过程将逐步... 目录1. html5 getUserMedia API简介1.1 API概念与历史1.2 功能与优势1.3

HTML5 搜索框Search Box详解

《HTML5搜索框SearchBox详解》HTML5的搜索框是一个强大的工具,能够有效提升用户体验,通过结合自动补全功能和适当的样式,可以创建出既美观又实用的搜索界面,这篇文章给大家介绍HTML5... html5 搜索框(Search Box)详解搜索框是一个用于输入查询内容的控件,通常用于网站或应用程

Java对异常的认识与异常的处理小结

《Java对异常的认识与异常的处理小结》Java程序在运行时可能出现的错误或非正常情况称为异常,下面给大家介绍Java对异常的认识与异常的处理,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参... 目录一、认识异常与异常类型。二、异常的处理三、总结 一、认识异常与异常类型。(1)简单定义-什么是