九章算法 | LinkedIn面试题：搜索区间

给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。

如果目标值不在数组中，则返回​[-1, -1]​

在线评测地址：LintCode 领扣

例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;
    }
}

更多题解参考：九章算法