[[429784]]

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

你可以假設數組中無重復元素。

示例 1:

• 輸入: [1,3,5,6], 5
• 輸出: 2

示例 2:

• 輸入: [1,3,5,6], 2
• 輸出: 1

示例 3:

• 輸入: [1,3,5,6], 7
• 輸出: 4

示例 4:

• 輸入: [1,3,5,6], 0
• 輸出: 0

思路

這道題目不難，但是為什么通過率相對來說并不高呢，我理解是大家對邊界處理的判斷有所失誤導致的。

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

搜索插入位置3

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

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

接下來我將從暴力的解法和二分法來講解此題，也借此好好講一講二分查找法。

暴力解法

暴力解題 不一定時間消耗就非常高，關鍵看實現的方式，就像是二分查找時間消耗不一定就很低，是一樣的。

C++代碼

class Solution { 
public: 
    int searchInsert(vector<int>& nums, int target) { 
        for (int i = 0; i < nums.size(); i++) { 
        // 分別處理如下三種情況 
        // 目標值在數組所有元素之前 
        // 目標值等于數組中某一個元素 
        // 目標值插入數組中的位置 
            if (nums[i] >= target) { // 一旦發現大于或者等于target的num[i]，那么i就是我們要的結果 
                return i; 
            } 
        } 
        // 目標值在數組所有元素之后的情況 
        return nums.size(); // 如果target是最大的，或者 nums為空，則返回nums的長度 
    } 
}; 

• 時間復雜度：O(n)
• 空間復雜度：O(1)

效率如下：

搜索插入位置

二分法

既然暴力解法的時間復雜度是O(n)，就要嘗試一下使用二分查找法。

搜索插入位置4

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

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

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

大體講解一下二分法的思路，這里來舉一個例子，例如在這個數組中，使用二分法尋找元素為5的位置，并返回其下標。

搜索插入位置5

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

相信很多同學對二分查找法中邊界條件處理不好。

例如到底是 while(left < right) 還是 while(left <= right)，到底是right = middle呢，還是要right = middle - 1呢?

這里弄不清楚主要是因為對區間的定義沒有想清楚，這就是不變量。

要在二分查找的過程中，保持不變量，這也就是循環不變量 (感興趣的同學可以查一查)。

二分法第一種寫法

以這道題目來舉例，以下的代碼中定義 target 是在一個在左閉右閉的區間里，也就是[left, right] (這個很重要)。

這就決定了這個二分法的代碼如何去寫，大家看如下代碼：

大家要仔細看注釋，思考為什么要寫while(left <= right)， 為什么要寫right = middle - 1。

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 在左區間，所以[left, middle - 1] 
            } else if (nums[middle] < target) { 
                left = middle + 1; // target 在右區間，所以[middle + 1, right] 
            } else { // nums[middle] == target 
                return middle; 
            } 
        } 
        // 分別處理如下四種情況 
        // 目標值在數組所有元素之前  [0, -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)的區間，如下代碼可以看出是如何在循環中堅持不變量的。

大家要仔細看注釋，思考為什么要寫while (left < right)， 為什么要寫right = middle。

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

• 時間復雜度：O(logn)
• 時間復雜度：O(1)

總結

希望通過這道題目，大家會發現平時寫二分法，為什么總寫不好，就是因為對區間定義不清楚。

確定要查找的區間到底是左閉右開[left, right)，還是左閉又閉[left, right]，這就是不變量。

然后在二分查找的循環中，堅持循環不變量的原則，很多細節問題，自然會知道如何處理了。

本文轉載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關注。轉載本文請聯系代碼隨想錄公眾號。