34 Search for a Range

34. Search for a Range​
1. Question
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(logn).
If the target is not found in the array, return[-1, -1].
For example,
Given[5, 7, 7, 8, 8, 10]and target value 8,
return[3, 4].
2. Implementation
(1) Binary Search
1
class Solution {
2
    public int[] searchRange(int[] nums, int target) {
3
        int[] res = {-1, -1};
4
​
5
        if (nums == null || nums.length == 0) {
6
            return res;
7
        }
8
​
9
        int start = 0, end = nums.length - 1, mid = 0;
10
​
11
        while (start + 1 < end) {
12
            mid = start + (end - start) / 2;
13
​
14
            if (nums[mid] < target) {
15
                start = mid + 1;
16
            }
17
            else {
18
                end = mid;
19
            }
20
        }
21
​
22
        if (nums[start] == target) {
23
            res[0] = start;
24
        }
25
        else if (nums[end] == target) {
26
            res[0] = end;
27
        }
28
        else {
29
            return res;
30
        }
31
​
32
        end = nums.length - 1;
33
​
34
        while (start + 1 < end) {
35
            mid = start + (end - start) / 2;
36
​
37
            if (nums[mid] > target) {
38
                end = mid - 1;
39
            }
40
            else {
41
                start = mid;
42
            }
43
        }
44
​
45
        if (nums[end] == target) {
46
            res[1] = end;
47
        }
48
        else if (nums[start] == target) {
49
            res[1] = start;
50
        }
51
        else {
52
            return res;
53
        }
54
        return res;
55
    }
56
}
Copied!
3. Time & Space Complexity
Binary Search: 时间复杂度O(logn), 空间复杂度O(1)

33 Search in Rotated Sorted Array

35 Search Insert Position

Last modified 2yr ago

Copy link

Contents

34. Search for a Range

1. Question

2. Implementation

3. Time & Space Complexity

34. Search for a Range​

1. Question

2. Implementation

3. Time & Space Complexity

34. Search for a Range