[[429784]]

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

你可以假設(shè)數(shù)組中無重復(fù)元素。

示例 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

思路

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

這道題目，要在數(shù)組中插入目標(biāo)值，無非是這四種情況。

搜索插入位置3

• 目標(biāo)值在數(shù)組所有元素之前
• 目標(biāo)值等于數(shù)組中某一個元素
• 目標(biāo)值插入數(shù)組中的位置
• 目標(biāo)值在數(shù)組所有元素之后

這四種情況確認(rèn)清楚了，就可以嘗試解題了。

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

暴力解法

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

C++代碼

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

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

效率如下：

搜索插入位置

二分法

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

搜索插入位置4

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

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

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

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

搜索插入位置5

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

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

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

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

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

二分法第一種寫法

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

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

大家要仔細(xì)看注釋，思考為什么要寫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在左閉右閉的區(qū)間里，[left, right] 
        while (left <= right) { // 當(dāng)left==right，區(qū)間[left, right]依然有效 
            int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2 
            if (nums[middle] > target) { 
                right = middle - 1; // target 在左區(qū)間，所以[left, middle - 1] 
            } else if (nums[middle] < target) { 
                left = middle + 1; // target 在右區(qū)間，所以[middle + 1, right] 
            } else { // nums[middle] == target 
                return middle; 
            } 
        } 
        // 分別處理如下四種情況 
        // 目標(biāo)值在數(shù)組所有元素之前  [0, -1] 
        // 目標(biāo)值等于數(shù)組中某一個元素  return middle; 
        // 目標(biāo)值插入數(shù)組中的位置 [left, right]，return  right + 1 
        // 目標(biāo)值在數(shù)組所有元素之后的情況 [left, right]， return right + 1 
        return right + 1; 
    } 
}; 

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

效率如下：

二分法第二種寫法

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

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

不變量是[left, right)的區(qū)間，如下代碼可以看出是如何在循環(huán)中堅持不變量的。

大家要仔細(xì)看注釋，思考為什么要寫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在左閉右開的區(qū)間里，[left, right)  target 
        while (left < right) { // 因為left == right的時候，在[left, right)是無效的空間 
            int middle = left + ((right - left) >> 1); 
            if (nums[middle] > target) { 
                right = middle; // target 在左區(qū)間，在[left, middle)中 
            } else if (nums[middle] < target) { 
                left = middle + 1; // target 在右區(qū)間，在 [middle+1, right)中 
            } else { // nums[middle] == target 
                return middle; // 數(shù)組中找到目標(biāo)值的情況，直接返回下標(biāo) 
            } 
        } 
        // 分別處理如下四種情況 
        // 目標(biāo)值在數(shù)組所有元素之前 [0,0) 
        // 目標(biāo)值等于數(shù)組中某一個元素 return middle 
        // 目標(biāo)值插入數(shù)組中的位置 [left, right) ，return right 即可 
        // 目標(biāo)值在數(shù)組所有元素之后的情況 [left, right)，return right 即可 
        return right; 
    } 
}; 

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

總結(jié)

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

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

然后在二分查找的循環(huán)中，堅持循環(huán)不變量的原則，很多細(xì)節(jié)問題，自然會知道如何處理了。

本文轉(zhuǎn)載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系代碼隨想錄公眾號。