大廠面試真題詳解：搜尋區間

給定一個包含 n 個整數的排序數組，找出給定目标值 target 的起始和結束位置。

如果目标值不在數組中，則傳回[-1, -1]

線上評測位址：[領扣題庫官網](

https://www.lintcode.com/problem/search-for-a-range/?utm_source=sc-tianchi-sz-20oct

)

例1:

輸入:
[]
9
輸出:
[-1,-1]           

例2:

輸入:
[5, 7, 7, 8, 8, 10]
8
輸出:
[3, 4]           

算法：二分

思路

• 由于給定的是一個有序數組，具有單調性，是以很容易想到二分。
• 二分查找target的第一次出現的位置和最後一次出現的位置，最後輸出即可。
• 具體實作：
• 對于一個長度為n的升序數組A，二分查找的區間為[0, n - 1]，定義left = 0, right = n - 1，中間值mid = left + (right - left) / 2 。

1. 當 A[mid] > target 時，顯然這時查找數值偏大，說明答案在左區間，是以使 right = mid 來縮小查找數值。
2. 當 A[mid] < target 時，顯然這時查找數值偏小，說明答案在右區間，是以使 left = mid 來放大查找數值。
3. 當 A[mid] == target 時，為了尋找target出現的最左端(第一次出現位置)時，我們選擇左區間作為下一次二分區間，是以使 right = mid；為了尋找target出現的最右端(最後一次出現位置)時，我們選擇右區間作為下一次二分區間，是以使 left = mid 。

• 綜上所述：
• 當我們尋找target的左端點即第一次出現的位置時：

1. 當 A[mid] < target 時， left = mid ；否則 right = mid。
2. 最後優先判斷并選取接近左邊的 left 再判斷 right

• 當我們尋找target的右端點即最後一次出現的位置時：

1. 當 A[mid] <= target 時， left = mid ；否則 right = mid。
2. 最後優先判斷并選取接近右邊的 right 再判斷 left

複雜度分析

• 常數級别的額外空間，空間複雜度O(1)。
• 兩個二分，時間複雜度O(logn)。

public class Solution {
    /**
     * @param A: an integer sorted array
     * @param target: an integer to be inserted
     * @return: a list of length 2, [index1, index2]
     */
    // 尋找左端點
    static int findFirstTargetNum(int[] A, int target, int n){
        int left = 0, right = n - 1;
        while (left + 1 < right){
            int mid = left + (right - left) / 2;
            if (A[mid] < target){
                left = mid;
            }
            else{
                right = mid;
            }
        }
        if (left < n && A[left] == target){
            return left;
        }
        if (right >= 0 && A[right] == target){
            return right;
        }
        return -1;
    }
    
    // 尋找右端點
    static int findLastTargetNum(int[] A, int target, int n){
        int left = 0, right = n - 1;
        while (left + 1 < right){
            int mid = left + (right - left) / 2;
            if (A[mid] <= target){
                left = mid;
            }
            else{
                right = mid;
            }
        }
        if (right >= 0 && A[right] == target){
            return right;
        }
        if (left < n && A[left] == target){
            return left;
        }
        return -1;
    }
    
    public int[] searchRange(int[] A, int target) {
        int n = A.length;
        int[] interval = {-1, -1};
        interval[0] = findFirstTargetNum(A, target, n);
        interval[1] = findLastTargetNum(A, target, n);
        return interval;
    }
}           

更多題解參考：

九章官網solution