AlgorithmJourney/LeetCode/LeetCode34.java at main · HenryJi529/AlgorithmJourney · GitHub

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import java.util.Arrays;

public class LeetCode34 {
    public static void main(String[] args) {
        int[] nums;
        int target;

        // 输入：nums = [5,7,7,8,8,10], target = 8
        // 输出：[3,4]
        nums = new int[] { 5, 7, 7, 8, 8, 10 };
        target = 8;
        System.out.println(Arrays.toString(new Solution34_2().searchRange(nums, target)));

        // 输入：nums = [5,7,7,8,8,10], target = 6
        // 输出：[-1,-1]
        nums = new int[] { 5, 7, 7, 8, 8, 10 };
        target = 6;
        System.out.println(Arrays.toString(new Solution34_2().searchRange(nums, target)));

        // 输入：nums = [], target = 0
        // 输出：[-1,-1]
        nums = new int[] {};
        target = 0;
        System.out.println(Arrays.toString(new Solution34_2().searchRange(nums, target)));
    }
}

class Solution34_1 {
    public int[] searchRange(int[] nums, int target) {
        int left = -1, right = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                left = i;
                break;
            }
        }
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] == target) {
                right = i;
                break;
            }
        }
        int[] result = { left, right };
        return result;
    }
}

class Solution34_2 {
    public int[] searchRange(int[] nums, int target) {
        int left = binarySearchLeft(nums, target);
        int right = binarySearchRight(nums, target);
        if (left > right) {
            return new int[] { -1, -1 };
        } else {
            return new int[] { left, right };
        }
    }

    public int binarySearchLeft(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        int mid;
        while (l <= r) {
            mid = l + (r - l) / 2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    public int binarySearchRight(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        int mid;
        while (l <= r) {
            mid = l + (r - l) / 2;
            if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
}