寫在前

對于二分查找關(guān)鍵是：確定二分查找的搜索區(qū)間，下面代碼（T704）中數(shù)組中元素唯一。不存在返回索引為-1。

class Solution {
    // 代碼1:搜索區(qū)間[l, r)
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }
    // 代碼2:搜索區(qū)間[l, r]
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }
}

如果數(shù)組中元素不唯一，我們需要找到重復(fù)元素的左右邊界（下邊有詳細題解T34），關(guān)鍵是我們找到目標值，不是選擇直接返回它的索引，而是繼續(xù)向一側(cè)縮小空間（具體哪一側(cè)需要看尋找哪個邊界）。

class Solution {
    // 代碼1:左邊界
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                // 當找到目標值，我們選擇繼續(xù)縮小左區(qū)間
                r = mid;
            }
        }
        return l;
    }
    // 代碼2:右邊界
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target) {
                r = mid;
            } else {
                // 當找到目標值，我們選擇繼續(xù)縮小右區(qū)間
                l = mid + 1;
            }
        }
        return l - 1;
    }
}

ps：上述采用左閉右開的寫法

• 上述的寫法中返回l和r無區(qū)別，因為循環(huán)的終止條件是 l == r;
• 為什么右邊界要減1呢？因為我們對 left 的更新必須是 l = mid + 1，就是說 while 循環(huán)結(jié)束時，nums[l] 一定不等于 target 了，而 nums[l-1] 可能是 target。
• 對于查找的元素不存在的情況可以單獨判斷。添加下面代碼判斷即可：

// 左邊界
if (l >= nums.length || nums[l] != target) {
  return -1;
}
// 右邊界
if (l == 0 || nums[l - 1] != target) {
  return -1;
}

1.搜索插入位置（35-易）

題目描述：排序數(shù)組中尋找目標值的索引，若不存在目標值，則返回目標值該插入的索引值。

示例：

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

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

思路：本題暴力解法為遍歷，但由于數(shù)組有序(題目假設(shè)無重復(fù)元素，二分法返回下標唯一)，也可以使用二分法減少時間復(fù)雜度，所以有序的數(shù)組都可以考慮使用二分查找。

法1.主要判斷當前值與目標值大小，相等或者大于目標值，返回當前索引值；小于目標值繼續(xù)遍歷循環(huán)。

法2.對于排序數(shù)組，我們要想到二分查找，時間復(fù)雜度O(logn)，這里主要注意二分法邊界的處理（更新區(qū)域的邊界）！

代碼1：暴力遍歷

public int searchInsert(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] < target) {
            continue;
        } else {
            // 是否插入在數(shù)組最前端
            if (i == 0) return 0;
            return i;
        }
    }
    return nums.length;
}

代碼2：二分查找

public int searchInsert(int[] nums, int target) {
    int l = 0, r = nums.length;
    while (l < r) {  //定義target在左閉右開的區(qū)間
        int m = l + ((r - l) >> 1);  
        if (nums[m] > target) {
            r = m;
        } else if (nums[m] < target) {
            l = m + 1;
        } else {
            return m;
        }
    }
    /**
    四種情況：
    1.target數(shù)組最前端，即[0,0), return 0
    2.target等于nums[m], return m
    -------------------------------
    3.target介于[l, r）之間，return r
    4.target在數(shù)組末端，return r
    **/
    return r;   
}

2.尋找重復(fù)數(shù)（287-中）

題目描述：數(shù)組元素取值范圍[1，n]，假設(shè)只有一個重復(fù)數(shù)（出現(xiàn)兩次或多次），找出這個重復(fù)數(shù)。

進階問題：

• 如何證明 nums 中至少存在一個重復(fù)的數(shù)字?
• 你可以在不修改數(shù)組 nums 的情況下解決這個問題嗎？
• 你可以只用常量級 O(1) 的額外空間解決這個問題嗎？
• 你可以設(shè)計一個時間復(fù)雜度小于 O(n^2) 的解決方案嗎？

示例：

輸入：nums = [1,3,4,2,2]
輸出：2
輸入：nums = [3,1,3,4,2]
輸出：3

思路：

法1.暴力遍歷元素兩兩比較，實現(xiàn)簡單，但時間復(fù)雜度O(n^2)；

法2.由于數(shù)組元素取值的特殊性，把數(shù)組看成鏈表結(jié)構(gòu)，把尋找重復(fù)值看成利用快慢指針尋找鏈表環(huán)的入口；

法3.值域的二分查找。最大值n，最小值1，記錄一個變量cnt，統(tǒng)計數(shù)組中小于等于mid的個數(shù)，根據(jù)個數(shù)與mid值的大小，二分確定重復(fù)值所在區(qū)間，時間復(fù)雜度O(nlogn)。

代碼1：雙指針

public int findDuplicate(int[] nums) {
    int slow = nums[0], fast = nums[nums[0]];
    while (slow != fast) {     //1.指針首次相遇退出循環(huán)（可能在環(huán)中某個位置）
        slow = nums[slow];
        fast = nums[nums[fast]];  
    }
    fast = 0;                  //2.快指針移到開始位置
    while (slow != fast) {     //3.快慢指針每次移動一步，指針再次相遇找到環(huán)入口，即重復(fù)值
        slow = nums[slow]; 
        fast = nums[fast];
    }  
    return slow;
}

代碼2：二分查找值域

public int findDuplicate(int[] nums) {
    int l = 1, r = nums.length - 1;
    while (l < r) {
        int mid = l + ((r - l) >> 1);
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= mid) {
                cnt++;      //1.每次遍歷數(shù)組，記錄小于mid元素的個數(shù)
            }
        }
        if (cnt > mid) {    //2.重復(fù)值在左區(qū)域，mid取大了
            r = mid;
        } else {
            l = mid + 1;    //3.重復(fù)值在右區(qū)域，mid取小了
        }
    }
    return l;
}

3.長度最小的子數(shù)組（209-中）

題目描述：返回數(shù)組中累加和大于等于給定值的最短連續(xù)子數(shù)組的長度。要求：時間復(fù)雜度O(nlogn)

示例：

輸入：s = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組。

思路：涉及連續(xù)子數(shù)組的問題，通常有兩種思路：滑動窗口和前綴和。

法1.滑動窗口，滑動窗口維護了滿足要求子數(shù)組：窗口右邊界更新累加和sum，若滿足條件，更新最小長度min，移動窗口的左邊界，更新此時sum，遍歷數(shù)組。

法2.前綴和+二分查找：本題每個元素都為正，保證前綴和一定是遞增的（升序）！

空間換時間：為了提高效率，我們創(chuàng)建數(shù)組sums來存儲前綴和，其中，sums[i]表示從nums[0]到nums[i - 1]的元素和。

目標：sums[k] - sums[i - 1] >= s，k - (i - 1)即滿足條件的子數(shù)組長度。如何求解最短的呢？將原目標轉(zhuǎn)化一下，即s + sums[i - 1] <= sums[k]，由于sums元素是遞增有序的，那么只要求出s + sums[i - 1]，二分查找這個下標K即可。

代碼1：滑動窗口

public int minSubArrayLen(int s, int[] nums) {
    int l = 0, r = 0; 
    int sum = 0;
    int min = Integer.MAX_VALUE;
    while (r < nums.length) {   
        sum += nums[r++];
        //滿足條件，找最短的子數(shù)組，注意使用while循環(huán)！
        while (sum >= s) {   
            min = Math.min(min, r - l);
            sum -= nums[l++];
        } 
    }
    return min == Integer.MAX_VALUE ? 0 : min;
}

代碼2：前綴和+二分查找

 public int minSubArrayLen(int s, int[] nums) {
    int n = nums.length;
    if (n == 0) return 0;
     
    int[] sums = new int[n];
    sums[0] = nums[0];
    for (int i = 1; i < n; i++) {
        sums[i] = nums[i] + sums[i - 1];
    }
     
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        int s2 = s - nums[i];
        //二分查找，目標值是 s2 + sums[i]
        int k = binarySearch(i, n - 1, sums, s2 + sums[i]);
        if (k != -1) {
            min = Math.min(min, k - i + 1);
        }

    }
    return min == Integer.MAX_VALUE ? 0 : min;
}

// 尋找大于等于 target 所有 sums 中最小的那個
private int binarySearch(int start, int end, int[] sums, int target) {
    int mid = -1;
    while (start < end) {
        mid = (start + end) >>> 1;
        if (sums[mid] >= target) {
            end = mid;
        } else {
            start = mid + 1;
        }
    }
    // 沒有找到返回 -1
    return sums[start] >= target ? start : -1;
}

另解：使用二分查找?guī)旌瘮?shù)：如果找到返回下標，如果沒有找到就返回一個負數(shù)，這個負數(shù)取反之后就是原數(shù)組中第一個比他大的值的下標（待插入位置）。

public int minSubArrayLen(int s, int[] nums) {
    int n = nums.length;
    int min = Integer.MAX_VALUE;
    int[] sums = new int[n + 1];
    for (int i = 1; i <= n; ++i) {
        sums[i] = nums[i - 1] + sums[i - 1];
    }

    for (int i = 0; i <= n; ++i) {
        int target = s + sums[i];
        int index = Arrays.binarySearch(sums, target);
        if (index < 0) index = ~index;
        if (index <= n) min = Math.min(min, index - i); 
    }
    return min == Integer.MAX_VALUE ? 0 : min;
}

4.有序矩陣的第K小的元素（378-中）

題目描述：找到方陣（行列元素都是升序）中排序后第k小的元素。

示例：

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

返回 13。

思路：目標：尋找矩陣中第k小的元素

法1.二分查找：類比287解法3。由于矩陣的有序性，可將整個值域進行二分查找。通過計算中間值mid，統(tǒng)計矩陣中小于等于這個值的元素有cnt個，當cnt<k，說明我們中間值取小了，否則，中間值取大了，通過調(diào)整值域一步步鎖定目標。優(yōu)化方案即240題思路，改變搜索的起始位置。

ps：為什么l == r返回的數(shù)值一定是矩陣中的值呢，首先明確一點我們mid是不一定在矩陣中的，只作為劃分值。

假設(shè)m為第k小的元素，s為第k + 1個，要使得有k個小于等于mid的元素，那么mid一定介于m和s之間，我們返回的是left，其實就是第一個滿足有k個小于等于自身的元素，那么m一定是第一個，所以left一定在矩陣中。

法2.大根堆：維護一個大根堆，當堆的大小>k，就彈出當前值，最后遍歷完矩陣，最終堆頂元素就是第k小的元素。注意：優(yōu)先級隊列默認使用小根，效率較低。

代碼1：二分查找值域，時間復(fù)雜度：O(n^2log(r - l))

public int kthSmallest(int[][] matrix, int k) {
    int m = matrix.length, n = matrix[0].length;
    int l = matrix[0][0], r = matrix[m - 1][n - 1];
    while (l < r) {    //第k小的元素一定在[l, r)之間，當l == r，找到第k小元素！??！
        int cnt = 0;   
        int mid = l + ((r - l) >> 1);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n && matrix[i][j] <= mid; j++) {
                cnt++;     //小于mid的元素個數(shù)
            }
        }
        if (cnt < k) {    //說明第k小元素在右半部分（mid取小了）
            l = mid + 1;
        } else {
            r = mid; 
        }
    }
    return l;   
}

優(yōu)化：利用矩陣的有序性，時間復(fù)雜度：O(nlog(r - l))

public int kthSmallest(int[][] matrix, int k) {
    int n = matrix.length;
    int left = matrix[0][0], right = matrix[n - 1][n - 1];
    while (left < right) {
        int mid = left + ((right - left) >> 1);
        if (check(matrix, mid, k, n)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

public boolean check(int[][] matrix, int mid, int k, int n) {
    int i = n - 1, j = 0;
    int cnt = 0;
    while (i >= 0 && j < n) {
        if (matrix[i][j] <= mid) {
            cnt += i + 1;
            j++;
        } else {
            i--;
        }
    }
    return cnt >= k;
}

代碼2：堆解法

public int kthSmallest(int[][] matrix, int k) {
    Queue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
    for (int i = 0; i < matrix.length; ++i) {
        for (int j = 0; j < matrix[0].length; ++j) {
            pq.add(matrix[i][j]);
            if (pq.size() > k) {
                pq.poll();
            }
        }
    }
    return pq.poll();
}

5.在排序數(shù)組中查找元素的第一個和最后一個位置（34-中）

題目描述：給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標值 target。找出給定目標值在數(shù)組中的開始位置和結(jié)束位置。如果數(shù)組中不存在目標值 target，返回 [-1, -1]。要求：時間復(fù)雜度O(logn)

示例：

輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]

思路：本題兩個關(guān)鍵點是數(shù)組有序和時間復(fù)雜度要求。所以使用二分查找。

對于二分查找，一定注意區(qū)間不變性，下邊代碼給出的查找區(qū)間尾[l, r)，當l == r退出循環(huán)。

• 若數(shù)組中存在目標值，那么不斷縮小查找區(qū)間，最終l指向一定是目標值
• 若不存在目標值，那么最終指向第一個滿足nums[mid] > target元素

注意：這里為了代碼簡潔，我們使用一個技巧找右邊界，就是找target + 1的左邊界，最后我們將找到的索引 - 1就是目標值的右邊界了。 對于找到的索引值，檢查是否滿足條件。

代碼：二分查找

public int[] searchRange(int[] nums, int target) {
    int first = binarySearch(nums, target);
    int last = binarySearch(nums, target + 1) - 1;   // 注意這里target不存在也不要緊，最后會在數(shù)組中找到比target + 1大的最小值的索引
    if (first == nums.length || nums[first] != target) {
        return new int[]{-1, -1};
    } else {
        return new int[]{first, Math.max(first, last)};
    }
}

private int binarySearch(int[] nums, int target) {
    int l = 0, r = nums.length; 
    while (l < r) {
        int m = l + (r - l) / 2;
        if (nums[m] >= target) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    return l;
}

6.在排序數(shù)組中查找單一元素（34-中）

題目描述：給定一個只包含整數(shù)的有序數(shù)組，每個元素都會出現(xiàn)兩次，唯有一個數(shù)只會出現(xiàn)一次，找出這個數(shù)。

思路：本題兩個關(guān)鍵點是數(shù)組有序和時間復(fù)雜度要求。所以使用二分查找。本質(zhì)是通過相鄰比較，因為單一元素破壞了有序?qū)?，從而確定目標元素的位置。

代碼實現(xiàn)：

class Solution {
    // 暴力解
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[n - 1];
    }

    // 二分查找（單一元素之后，成對的狀態(tài)被破壞）
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            // l, m 和 r 都應(yīng)該落在偶數(shù)位置
            if (mid % 2 == 1) {
                mid--;
            } 
            if (nums[mid] == nums[mid + 1]) {
                l = mid + 2;
            } else {
                r = mid;
            }
        }
        return nums[l];
    }

    // 二分查找優(yōu)化（mid為奇與左邊比較，偶數(shù)與右邊比較）
        public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == nums[mid ^ 1]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return nums[l];
    }
}

7.在排序數(shù)組中查找單一元素（34-中）

題目描述：給定兩個大小分別為 m 和 n 的正序（從小到大）數(shù)組 nums1 和 nums2。請你找出并返回這兩個正序數(shù)組的 中位數(shù) 。

思路：參考@Terry2020，本題轉(zhuǎn)化一下就是有序數(shù)組尋找第k小的數(shù)。

• 遞歸出口：當K=1時候，相當于求最小值，我們只要比較nums1和nums2的起始位置i和j上的數(shù)字就可以了。

• 一般情況：取兩個數(shù)組中的第k/2個元素（midVal1和midVal2）進行比較，如果midVal1 < midVal2，則說明數(shù)組1中的前k/2個元素不可能成為第k個元素的候選，所以將數(shù)組1中的前k/2個元素去掉，作為新數(shù)組和數(shù)組2求第k-k/2小的元素，因為我們把前k/2個元素去掉了，所以相應(yīng)的k值也應(yīng)該減少k/2。midVal1 > midVal2的情況亦然。

• 邊界問題：

  • 當某一個數(shù)組的起始位置大于等于其數(shù)組長度時，說明其所有數(shù)字均已經(jīng)被淘汰了，相當于一個空數(shù)組了，那么實際上就變成了在另一個數(shù)組中找數(shù)字，直接就可以找出來了。
  • 由于兩個數(shù)組的長度不定，所以有可能某個數(shù)組元素數(shù)不足k/2，所以我們需要先檢查一下，數(shù)組中到底存不存在第K/2個數(shù)字，如果存在就取出來，否則就賦值上一個整型最大值，這樣肯定會大于另一個數(shù)組的第k/2個元素，從而把另一個數(shù)組的前k/2個元素淘汰。

ps：賦予整型最大值的意思只是說如果第一個數(shù)組的K/2不存在，則說明這個數(shù)組的長度小于K/2，那么另外一個數(shù)組的前K/2個我們是肯定不要的。例如，加入第一個數(shù)組長度是2，第二個數(shù)組長度是12，則K為7，K/2為3，因為第一個數(shù)組長度小于3，則無法判斷中位數(shù)是否在其中，而第二個數(shù)組的前3個肯定不是中位數(shù)！

使用一個小trick，可以避免討論奇偶：我們分別找第 (m+n+1)/2個數(shù)，和(m+n+2)/2個數(shù)，然后求其平均值即可，這對奇偶數(shù)均適用。假如 m+n 為奇數(shù)的話，那么其實 (m+n+1) / 2 和 (m+n+2) / 2 的值相等，相當于兩個相同的數(shù)字相加再除以2，還是其本身。

代碼實現(xiàn)：

class Solution {
    // 暴力解：時間復(fù)雜度O(m + n) 空間復(fù)雜度O(m + n)
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] mergeArray = new int[m + n];
        int index = 0;
        int i = 0, j = 0;

        while (i < m && j < n) {
            mergeArray[index++] = nums1[i] > nums2[j] ? nums2[j++] : nums1[i++];
        } 
        while (i < m) {
            mergeArray[index++] = nums1[i++];
        }
        while (j < n) {
            mergeArray[index++] = nums2[j++];
        }

        int midIdx = m + n >> 1;
        return (m + n) % 2 == 1 ? (double) mergeArray[midIdx] : 
        ((double) mergeArray[midIdx] + (double) mergeArray[midIdx - 1]) / 2;
    }

    // 二分查找（尋找第k小的數(shù)）
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        // 尋找中位數(shù)
        int left = (m + n + 1) / 2;
        int right = (m + n +2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }

    /**
        findKth:兩個有序數(shù)組找第k個元素
        i:nums1的起始位置
        j:nums2的起始位置
     */
    private int findKth(int[] nums1, int i, int[] nums2, int j, int k) {
        if (j == nums2.length) {
            return nums1[i + k - 1];
        }
        if (i == nums1.length) {
            return nums2[j + k - 1];
        }
        // 遞歸出口
        if (k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }
        // 找這兩個數(shù)組的第k/2小的數(shù)字，不足K/2個數(shù)字，賦值整形最大值，以便淘汰另一個數(shù)組的前K/2個數(shù)字
        int midVal1 = (i + k/2 - 1) < nums1.length ? nums1[i + k/2 - 1] : Integer.MAX_VALUE;
        int midVal2 = (j + k/2 - 1) < nums2.length ? nums2[j + k/2 - 1] : Integer.MAX_VALUE;
        // 核心邏輯
        if (midVal1 < midVal2) {
            return findKth(nums1, i + k/2, nums2, j, k - k/2);
        } else {
            return findKth(nums1, i, nums2, j + k/2, k - k/2);
        }
    }
}

8.在排序數(shù)組中查找單一元素（34-中）

思路分析：由于調(diào)用次數(shù)限制，并且數(shù)組在山頂?shù)膬蛇厙栏竦纳蚧蛘呓敌?。所以可以使用二分查找?/p>

• 二分查找找到峰頂索引
• 分別對左右兩邊進行二分查找（技巧：利用flag標記升序還是降序）

代碼實現(xiàn)：

/**
 * // This is MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface MountainArray {
 *     public int get(int index) {}
 *     public int length() {}
 * }
 */
 
class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int n = mountainArr.length();
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (mountainArr.get(mid) <mountainArr.get(mid + 1)) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }

        int index = binarySearch(target, mountainArr, 0, l, true);
        return index != -1 ? index : binarySearch(target, mountainArr, l + 1, n - 1, false);
    }

    public int binarySearch(int target, MountainArray mountainArr, int l, int r, boolean flag) {
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (mountainArr.get(mid) == target) {
                return mid;
            }
            if (mountainArr.get(mid) < target) {
                l = flag ? mid + 1 : l;
                r = flag ? r : mid - 1;
            } else {
                r = flag ? mid - 1 : r;
                l = flag ? l : mid + 1;
            }
        }
        return -1;

    }
}