二分法我們還需要再練習練習
給定一個排序數組和一個目標值，在數組中找到目標值，并返回其索引。如果目標值不存在于數組中，返回它將會被按順序插入的位置。
你可以假設數組中無重復元素。
示例 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]，這就是不變量。
然后在二分查找的循環中，堅持循環不變量的原則，很多細節問題，自然會知道如何處理了。
本文轉載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關注。轉載本文請聯系代碼隨想錄公眾號。
