给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。 如果目标值不在数组中，则返回[-1, -1]

在线评测地址

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

更多题解参考