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

🍕前面的話🥞

大家好！本篇文章将介紹代碼随想錄的題，本文将以2道題作為背景，介紹二分查找，展示語言為java（部落客學習語言為java)。今天呢，是部落客開始刷力扣的第十天，如果有想要開始準備自己的算法面試的同學，可以跟着我的腳步一起，共同進步。大家都是并肩作戰的夥伴，一起努力奮力前行，路漫漫其修遠兮，吾将上下而求索，相信我們一定都可以拿到自己期望的offer，沖沖沖！

👩‍💻部落格首頁：京與舊鋪的部落格首頁

✨歡迎關注🖱點贊🎀收藏⭐留言✒

🔮本文由京與舊鋪原創

😘系列專欄：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

🌮源代碼

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;
    }
}

🎏思路

考慮使用二分查找來優化方法二中的搜尋過程。因為 \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 的平方根

給你一個非負整數

，計算并傳回

的算術平方根。

由于傳回類型是整數，結果隻保留整數部分，小數部分将被舍去。

**注意：**不允許使用任何内置指數函數和算符，例如

pow(x, 0.5)

或者

x ** 0.5

。

示例 1：

輸入：x = 4
輸出：2

示例 2：

輸入：x = 8
輸出：2
解釋：8 的算術平方根是 2.82842..., 由于傳回類型是整數，小數部分将被舍去。

👸源代碼

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：

輸入: 4

輸出: 2

這是顯然的，44 本身是一個完全平方數，2^2 = 42

2

=4。雖然在數學上一個數的平方根有正有負，但是這個題目隻要求我們傳回算術平方根。

示例 2 ：

輸入: 8

輸出: 2

因為 88 的平方根實際上是 2.828422.82842，題目要求我們将小數部分舍去。是以輸出 22。于是我們知道：由于輸出結果的時候，需要将小數部分舍去，是以問題的答案，平方以後一定不會嚴格大于輸入的整數。這裡傳回 33 就不對了，這是因為 3^2 = 9 > 83

2

=9>8。

思路分析

從題目的要求和示例我們可以看出，這其實是一個查找整數的問題，并且這個整數是有範圍的。

如果這個整數的平方恰好等于輸入整數，那麼我們就找到了這個整數；

如果這個整數的平方嚴格大于輸入整數，那麼這個整數肯定不是我們要找的那個數；

如果這個整數的平方嚴格小于輸入整數，那麼這個整數可能是我們要找的那個數（重點了解這句話）。

是以我們可以使用「二分查找」來查找這個整數，不斷縮小範圍去猜。

猜的數平方以後大了就往小了猜；

猜的數平方以後恰恰好等于輸入的數就找到了；

猜的數平方以後小了，可能猜的數就是，也可能不是。

很容易知道，題目要我們傳回的整數是有範圍的，直覺上一個整數的平方根肯定不會超過它自己的一半，但是 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 也可以。

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