力扣刷题--数组--第三天

今天再做两道二分查找的题目，关于二分查找的知识可看我前两篇博客。话不多说，直接开干！

题目1：69.x 的平方根
题目详情：
  给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
  注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：
输入：x = 4
输出：2
示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
 
提示：
0 <= x <= pow(2,31)-1

解题思路：
  看到题首先想到的估计就是暴力求解吧，循环找到最接近x的索引，写完提交发现：

  额，我只打败了9.07%的python3用户，哈哈哈哈，我真是个菜鸡。如果这道题使用二分查找怎么做呢，我开始还想着建立一个从$0\ast 0$到$x\ast x$的值数组，然后将x视为target，使用二分查找即可，后来看了题解才发现大可不必。无需先生成一个数组。具体见代码：

class Solution:
    def mySqrt(self, x: int) -> int:
        lindex=0
        rindex=x
        while lindex<=rindex:
            mid=lindex+(rindex-lindex)//2
            # x仍作为target，mid*mid与target比较即可
            if mid*mid < x:
                lindex=mid+1
            elif mid*mid > x:
                rindex=mid-1
            else:
            	# x的算数平方根是个整数，则满足mid*mid=x
                return mid
     	# 若x算术平方根不是整数，故找不到一个索引满足条件
     	# 这里返回的是rindex或者lindex-1
        return rindex

  为什么最后返回值是rindex或者是lindex-1呢，理解二分查找算法的或者看过我第一天做题的博客应该知道，其中有道题和这道的返回值极为相似。当跳出循环时，满足rindex<lindex且rindex+1=lindex。在lindex左边的值一定都小于x的算法平方根，lindex是第一个大于x的算法平方根的索引，因为最终取算法平方根的整数部分，故返回的应该是lindex-1。同理可以从rindex的角度推得最终返回rindex。

题目2：367. 有效的完全平方数
题目详述：
  给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
  不能使用任何内置的库函数，如 sqrt 。

示例 1：
输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。
示例 2：

输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。
 
提示：
1 <= num <= pow(2,31)-1

解题思路：
  这道题和上面那道完全一样，返回值更加简单，不再详述。

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        lindex=0
        rindex=num
        while lindex<=rindex:
            mid=lindex+(rindex-lindex)//2
            if mid*mid > num:
                rindex=mid-1
            elif mid*mid < num:
                lindex=mid+1
            else:
                return True
        return False