力扣每日一练之二分查找Day10

🍕前面的话🥞

大家好！本篇文章将介绍代码随想录的题，本文将以2道题作为背景，介绍二分查找，展示语言为java（博主学习语言为java)。今天呢，是博主开始刷力扣的第十天，如果有想要开始准备自己的算法面试的同学，可以跟着我的脚步一起，共同进步。大家都是并肩作战的伙伴，一起努力奋力前行，路漫漫其修远兮，吾将上下而求索，相信我们一定都可以拿到自己期望的offer，冲冲冲！

👩‍💻博客主页：京与旧铺的博客主页

✨欢迎关注🖱点赞🎀收藏⭐留言✒

🔮本文由京与旧铺原创，csdn首发！

😘系列专栏：java学习

💻首发时间：🎞2022年5月24日🎠

🎨你做三四月的事，八九月就会有答案，一起加油吧

🔏参考在线编程网站：🎧力扣

🀄如果觉得博主的文章还不错的话，请三连支持一下博主哦

🎧最后的话，作者是一个新人，在很多方面还做的不好，欢迎大佬指正，一起学习哦，冲冲冲

🏓导航小助手📻

文章目录

• 力扣每日一练之二分查找Day10
• • @[toc]
• 🍞Leetcode 367.有效的完全平方数
• 🌮源代码
• 🎏思路
• [🌮69. x 的平方根 ](https://leetcode.cn/problems/sqrtx/)
• 👸源代码
• 🧈思路

---

🍞Leetcode 367.有效的完全平方数

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16
输出：true
示例 2：

输入：num = 14
输出：false
1
2
3
4
5
6
7
8

🌮源代码

class Solution {
    public boolean isPerfectSquare(int num) {
         int left=0,right=num;
         while(left<=right){
             int mid=left+(right-left)/2;
             long square=(long)mid*mid;
             if(square<num){
                 left=mid+1;
             }else if(square>num){
                 right=mid-1;
             }else {
                 return true;
             }
         }
         return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

🎏思路

考虑使用二分查找来优化方法二中的搜索过程。因为 \textit{num}num 是正整数，所以若正整数 xx 满足 x \times x = \textit{num}x×x=num，则 xx 一定满足 1 \le x \le \textit{num}1≤x≤num。于是我们可以将 11 和 \textit{num}num 作为二分查找搜索区间的初始边界。

细节

因为我们在移动左侧边界 \textit{left}left 和右侧边界 \textit{right}right 时，新的搜索区间都不会包含被检查的下标 \textit{mid}mid，所以搜索区间的边界始终是我们没有检查过的。因此，当\textit{left} = \textit{right}left=right 时，我们仍需要检查 \textit{mid} = (\textit{left}+\textit{right}) / 2mid=(left+right)/2。

🌮69. x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

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

**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

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

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
1
2
3

👸源代码

class Solution {
    public int mySqrt(int x) {
        if(x==0){
            return 0;
        }
          if(x==1){
              return 1;
          }
          int left=1;
          int right=x/2;
          while(left<right){
              int mid=left+(right-left+1)/2;
              if(mid>x/mid){
                  right=mid-1;
              }else{
                  left=mid;
              }
          }
          return left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

🧈思路

题意分析

这道题要求我们实现平方根函数，输入是一个非负整数，输出也是一个整数；
但是题目当中说：结果只保留整数的部分，小数部分将被舍去。这是什么意思呢？我们分析一下示例。

示例 1：


输入: 4
输出: 2
这是显然的，44 本身是一个完全平方数，2^2 = 42 
2
=4。虽然在数学上一个数的平方根有正有负，但是这个题目只要求我们返回算术平方根。

示例 2 ：

 
输入: 8
输出: 2
因为 88 的平方根实际上是 2.828422.82842，题目要求我们将小数部分舍去。因此输出 22。于是我们知道：由于输出结果的时候，需要将小数部分舍去，因此问题的答案，平方以后一定不会严格大于输入的整数。这里返回 33 就不对了，这是因为 3^2 = 9 > 83 
2
=9>8。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

思路分析
从题目的要求和示例我们可以看出，这其实是一个查找整数的问题，并且这个整数是有范围的。

如果这个整数的平方 恰好等于 输入整数，那么我们就找到了这个整数；
如果这个整数的平方 严格大于 输入整数，那么这个整数肯定不是我们要找的那个数；
如果这个整数的平方 严格小于 输入整数，那么这个整数 可能 是我们要找的那个数（重点理解这句话）。
因此我们可以使用「二分查找」来查找这个整数，不断缩小范围去猜。

猜的数平方以后大了就往小了猜；
猜的数平方以后恰恰好等于输入的数就找到了；
猜的数平方以后小了，可能猜的数就是，也可能不是。
很容易知道，题目要我们返回的整数是有范围的，直觉上一个整数的平方根肯定不会超过它自己的一半，但是 00 和 11 除外，因此我们可以在 11 到输入整数除以 22 这个范围里查找我们要找的平方根整数。00 单独判断一下就好。

对代码编写逻辑的解释：

一、写 if 和 else 的原因：

猜的数是 mid ，根据上面的分析，如果 mid 的平方 严格大于 x，mid 肯定不是解，比 mid 大的整数也肯定不是解，因此问题的答案只可能存在区间 [left…mid - 1]，此时设置 right = mid - 1；
else 的情况就是 if 的反面，只要 if 的分支和对应的区间分析对了，else 的区间是 [left…mid - 1] 的反面区间，即 [mid…right] ，此时设置 left = mid。
二、为什么最后返回 left。

退出 while (left < right) 循环的时候，由于边界搜索是 left = mid 与 right = mid - 1，因此退出循环的时候一定有 left 与 right 重合，返回 right 也可以。

ft…mid - 1] 的反面区间，即 [mid…right] ，此时设置 left = mid。