034.Search for a Range

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
[]
0
[5, 7, 7, 8, 8, 10]
8
[5, 7, 7, 8, 10]
8
[2,2,3,4,4,4,4,4,4,4,4,5,6,7]
4
[4,4,4,4,4,4,5]
4
[4,4,4,4,4,4,4,5]
5
[4,5,5,5,5,5]
4
[2,3,4,4,4,5,6,7]
1

Solution 1: accepted 7ms

Binary search with wildcard while (lo + 1 < hi) plus final conditions.

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
public int[] searchRange(int[] nums, int target) {
    int lo = 0;
    int hi = nums.length - 1;
    if (hi < 0) return new int[] {-1, -1};
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > target) {
            hi = mid;
        } else if (nums[mid] < target) {
            lo = mid;
        } else {
            if (nums[lo] != target) {
                lo++;
            } else if (nums[hi] != target) {
                hi--;
            } else {
                return new int[] {lo, hi};
            }
        }
    }
    if (nums[lo] == target && nums[hi] == target)
        return new int[] {lo, hi};
    if (nums[lo] == target)
        return new int[] {lo, lo};
    else if (nums[hi] == target)
        return new int[] {hi, hi};
    else
        return new int[] {-1, -1};
}

Alternative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[] searchRange(int[] nums, int target) {
    int lo = 0;
    int hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > target) {
            hi = mid - 1;
        } else if (nums[mid] < target) {
            lo = mid + 1;
        } else {
            if (nums[lo] != target) {
                lo++;
            } else if (nums[hi] != target) {
                hi--;
            } else {
                return new int[] {lo, hi};
            }
        }
    }
    return new int[] {-1, -1};
}