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

🍕前面的話🥞

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

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

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

🔮本文由京與舊鋪原創

😘系列專欄：java學習

💻首發時間：🎞2022年5月11日🎠

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

🔏參考線上程式設計網站：🎧力扣

🀄如果覺得部落客的文章還不錯的話，請三連支援一下部落客哦

🎧最後的話，作者是一個新人，在很多方面還做的不好，歡迎大佬指正，一起學習哦，沖沖沖

💬推薦一款模拟面試、刷題神器👉點選進入網站

🏓導航小助手📻

文章目錄

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

@[toc]

🎀Leetcode704.二分查找
🎏源代碼
🧶解題思路
🎡LeetCode278.第一個錯誤的版本
🎑源代碼
🎎解題思路
🧥Leetcode35.搜尋輸入位置
👠源代碼
🥾解題思路
🌌總結

覺得文章寫的不錯的親親，點贊評論關注走一波，愛你們哦🛴

🎀Leetcode704.二分查找

給定一個 n 個元素有序的（升序）整型數組 nums 和一個目标值 target ，寫一個函數搜尋 nums 中的 target，如果目标值存在傳回下标，否則傳回 -1。

示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現在 nums 中并且下标為 4
示例 2:

輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中是以傳回 -1

🎏源代碼

class Solution {
    public int search(int[] nums, int target) {
        int low=0,high=nums.length-1;
        while(low<=high){
            int mid=(high-low)/2+low;
            int num=nums[mid];
            if(num==target){
                return mid;
            }else if(num<target){
                low=mid+1;
            }else{
                high=mid-1;
            }
        }
        return -1;
    }
}

🧶解題思路

設定左右指針

找出中間位置，并判斷該位置值是否等于 target

nums[mid] == target 則傳回該位置下标

nums[mid] > target 則右側指針移到中間

nums[mid] < target 則左側指針移到中間

🎡LeetCode278.第一個錯誤的版本

你是産品經理，目前正在帶領一個團隊開發新的産品。不幸的是，你的産品的最新版本沒有通過品質檢測。由于每個版本都是基于之前的版本開發的，是以錯誤的版本之後的所有版本都是錯的。

假設你有 n 個版本 [1, 2, …, n]，你想找出導緻之後所有版本出錯的第一個錯誤的版本。

你可以通過調用 bool isBadVersion(version) 接口來判斷版本号 version 是否在單元測試中出錯。實作一個函數來查找第一個錯誤的版本。你應該盡量減少對調用 API 的次數。

示例 1：

輸入：n = 5, bad = 4
輸出：4
解釋：
調用 isBadVersion(3) -> false 
調用 isBadVersion(5) -> true 
調用 isBadVersion(4) -> true
是以，4 是第一個錯誤的版本。
示例 2：

輸入：n = 1, bad = 1
輸出：1

🎑源代碼

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left=1,right=n;
        while(left<right){
            int mid=left+(right-left)/2;
            if(isBadVersion(mid)){
                right=mid;
            }else{
                left=mid+1;
            }
            
        }
        return left;
    }
}

🎎解題思路

因為題目要求盡量減少調用檢查接口的次數，是以不能對每個版本都調用檢查接口，而是應該将調用檢查接口的次數降到最低。

注意到一個性質：當一個版本為正确版本，則該版本之前的所有版本均為正确版本；當一個版本為錯誤版本，則該版本之後的所有版本均為錯誤版本。我們可以利用這個性質進行二分查找。

具體地，将左右邊界分别初始化為 11 和 nn，其中 nn 是給定的版本數量。設定左右邊界之後，每次我們都依據左右邊界找到其中間的版本，檢查其是否為正确版本。如果該版本為正确版本，那麼第一個錯誤的版本必然位于該版本的右側，我們縮緊左邊界；否則第一個錯誤的版本必然位于該版本及該版本的左側，我們縮緊右邊界。

這樣我們每判斷一次都可以縮緊一次邊界，而每次縮緊時兩邊界距離将變為原來的一半，是以我們至多隻需要縮緊 O(\log n)O(logn) 次。

🧥Leetcode35.搜尋輸入位置

給定一個排序數組和一個目标值，在數組中找到目标值，并傳回其索引。如果目标值不存在于數組中，傳回它将會被按順序插入的位置。

請必須使用時間複雜度為 O(log n) 的算法。

示例 1:

輸入: nums = [1,3,5,6], target = 5
輸出: 2
示例 2:

輸入: nums = [1,3,5,6], target = 2
輸出: 1
示例 3:

輸入: nums = [1,3,5,6], target = 7
輸出: 4

👠源代碼

class Solution {
    public int searchInsert(int[] nums, int target) {
         int left=0,right=nums.length-1;
         while(left<=right){
             int mid=left+(right-left)/2;
             if(nums[mid]==target){
                 return mid;
             }else if(nums[mid]<target){
                 left=mid+1;
             }else{
                 right=mid-1;
             }
         }
         return left;
    }
}

🥾解題思路

如果該題目暴力解決的話需要 O(n)O(n) 的時間複雜度，但是如果二分的話則可以降低到 O(logn)O(logn) 的時間複雜度

整體思路和普通的二分查找幾乎沒有差別，先設定左側下标 left 和右側下标 right，再計算中間下标 mid

每次根據 nums[mid] 和 target 之間的大小進行判斷，相等則直接傳回下标，nums[mid] < target 則 left 右移，nums[mid] > target 則 right 左移

查找結束如果沒有相等值則傳回 left，該值為插入位置

時間複雜度：O(logn)O(logn)

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