二分法其實很簡單，為什麼老是寫不對！！

  • 2020 年 7 月 17 日
  • 筆記

相信很多人對二分法是又愛又恨，愛是在於它思想簡單，效率確實高， 恨是恨在為什麼總是寫不對呢

二分查找涉及的很多的邊界條件，邏輯比較簡單，就是寫不好

甚至有的同學乾脆把二分法背來了得了

其實背過的同學應該會有體會，硬背二分法，過一段時間依然會寫錯

例如 循環中到底是 小於 還是 小於等於， 到底是+1 呢，還是要-1呢

這是為什麼呢，主要是我們對區間的定義沒有想清楚，這就是我們的不變數

我們要在二分查找的過程中，保持不變數，這也就是循環不變數 （感興趣的同學可以查一查）

接下來我通過leetcode上一道面試題，來讓大家一次性徹底掌握二分法

題目是leetcode編號35的面試題. 搜索插入位置

 

題目地址:

分析題目

這道題目，我們要在數組中插入目標值，無非是這四種情況

 

 

  • 目標值在數組所有元素之前
  • 目標值等於數組中某一個元素
  • 目標值插入數組中的位置
  • 目標值在數組所有元素之後

這四種情況確認清楚了，我們就可以嘗試解題了

暴力解法思路很直接，就是for循環遍歷一下，時間複雜度是O(n)

既然暴力解法的時間複雜度是On，我們就要嘗試一下使用二分查找法。

二分法

大家注意這道題目的前提是數組是有序數組，這也是使用二分查找的基礎條件

以後大家只要看到面試題里給出的數組是有序數組，都可以想一想是否可以使用二分法。

同時題目還強調數組中無重複元素，因為一旦有重複元素，使用二分查找法返回的元素下表可能不是唯一的。

下圖來闡述一下二分法的大體思路，例如在這個數組中，我們使用二分法尋找元素為5的位置，並返回其下標，如下圖

 

  1. 開始左邊界為0，右邊界下表為7，那麼中間位置下表是3， arr[3] > 5
  2. 左區間為我們下一步的查找範圍，
  3. 左邊界為0，右邊界為2，中間位置下表為1 arr[1] < 5
  4. 右區間為我們下一步的查找範圍
  5. 左邊界2，右邊界2，a[2] == 5，
  6. 返回下表2。

接下來呢我們來看一下二分法具體實現

二分法第一種寫法

我們定義 target 是在一個在左閉右閉的區間里，也就是[left, right]

這就決定了我們 這個二分法的程式碼如何去寫，大家看如下程式碼

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n - 1; // 我們定義target在左閉右閉的區間里，[left, right]，這個區間的定義就是我們的不變數，接下來，要在下面的循環中，堅持這個不變數，我們就知道其中的邊界條件應該怎麼判斷了
        while (left <= right) { // 為什麼是<=呢，因為當left==right，區間[left, right]依然有效
            int middle = left + ((right - left) / 2);// 防止溢出 等同於(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左區間，因為我們的區間是左閉右閉的區間，nums[middle]一定不是我們的目標值，所以在right = middle - 1在[left, middle - 1]區間中繼續尋找目標值
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右區間，所以[middle + 1, right]
            } else { // nums[middle] == target
                return middle;
            }
        }
        // 分別處理如下四種情況
        // 目標值在數組所有元素之前，此時區間為[0, -1]，所以return right + 1
        // 目標值等於數組中某一個元素  return middle;
        // 目標值插入數組中的位置，一定是我們查找的範圍 [left, right]之後，return  right + 1
        // 目標值在數組所有元素之後的情況，也是我們查找的範圍 [left, right]之後， return right + 1
        return right + 1;
    }
};

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

效率如下：

 

二分法第二種寫法

如果說我們定義 target 是在一個在左閉右開的區間里，也就是[left, right)

那麼二分法的邊界處理方式則截然不同。

不變數是[left, right)的區間，如下程式碼可以看出是如何在循環中堅持不變數的。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0;
        int right = n; // 我們定義target在左閉右開的區間里，[left, right)  這是
        while (left < right) { // 因為left == right的時候，在[left, right)是無效的空間
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左區間，因為是左閉右開的區間，nums[middle]一定不是我們的目標值，所以right = middle，在[left, middle)中繼續尋找目標值
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右區間，在 [middle+1, right)中
            } else { // nums[middle] == target
                return middle; // 數組中找到目標值的情況，直接返回下標
            }
        }
        // 分別處理如下四種情況
        // 目標值在數組所有元素之前，此時區間為 [0,0)，所以可以return right
        // 目標值等於數組中某一個元素 return middle
        // 目標值插入數組中的位置 [left, right) ，return right 即可
        // 目標值在數組所有元素之後的情況 [left, right)，return right 即可
        return right;
    }
};

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

總結

從上面兩種二分法的程式碼中，我們可以看到是如何處理二分查找過程中的邊界情況

很多同學二分寫不好，就是因為邊界總是不知道 該是<= 還是< 呢，

是 right = middle – 1呢 還是 right = middle呢

這都是因為沒有意識到去區間的定義，區間的定義就是我們的不變數

在二分部查找的過程只要遵循著區間的定義也就是這個不變數

我們就可以很輕鬆的寫出二分法

以上講解大家應該對二分法中循環不變數有一個直觀的感受

理解的查找區間的定義（不變數），然後在二分循環中遇到了不知該如何處理的邊界條件的時候

就去想一下 我們區間的定義，這樣就知道邊界條件應該如何去寫了

通過這次講解希望幫助大家可以徹底理解二分法！

VirMach 便宜 VPS

QNews

QNews