34. Find First and Last Position of Element in Sorted Array

Posted on Edited on In Words count: 1.9k Reading time ≈ 2 mins.

34. Find First and Last Position of Element in Sorted Array

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
27
28
29
Given an array of integers nums sorted in non-decreasing order, find the starting and ending 
position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Example 3:

Input: nums = [], target = 0
Output: [-1,-1]
 

Constraints:

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums is a non-decreasing array.
-109 <= target <= 109

难度 : Medium

思路

用BinarySearch的lowerbound来找到对应的位置

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[]{-1,-1};
        int l = lower(nums, target);
        int r = lower(nums, target+1) - 1;
        if (l <= r) {
            return new int[]{l,r};
        }
        return ans;
    }
    private int lower(int[] nums, int target) {
        int n = nums.length;
        int l = 0;
        int r = n;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

用lowerbound和upperbound

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int[] searchRange(int[] nums, int target) {
        
        if (nums == null || nums.length == 0) {
            return new int[]{-1,-1};
        }
        int l = lower(nums, target);        
        int r = upper(nums, target);
        return l > r ? new int[]{-1,-1} : new int[]{l,r};
    }
    
    private int lower(int[] nums, int target) {
        int l = 0;
        int r = nums.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            //f(m) = nums[m] >= target
            if (nums[m] >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        //l 最小值 使得 nums[m] >= target
        //l 是最小值 满足f(m)
        return l;
    }
    //第一个数严格大于target
    private int upper(int[] nums, int target) {
        int l = 0;
        int r = nums.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] > target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l - 1;
    }
}