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

本文主要是介绍二分搜索小结-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