LC.P34[在排序数组中查找元素的第一个和最后一个位置]

方法一：二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[]{-1, -1};
        int n = nums.length;
        if (n == 0) return ans;
        // 查找左边界
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + right >> 1;
            if (nums[mid] >= target) right = mid;
            else left = mid + 1;
        }
        if (nums[right] != target) return ans;
        ans[0] = right;
        // 查找右边界
        left = 0;
        right = n - 1;
        while (left < right) {
            int mid = left + right + 1 >> 1;
            if (nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        ans[1] = right;
        return ans;
    }
}
  • 时间复杂度：$O(logn)$
  • 空间复杂度：$O(1)$