LeetCode/FirstLast.java at main · JBecnel/LeetCode · 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
// https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/
public class FirstLast {
    public static void main(String[] args) {
        FirstLast fl = new FirstLast();
        int[] nums = new int[]{5,7,7,8,8,10};
        fl.printArray(fl.searchRange(nums, 8));
        fl.printArray(fl.searchRange(nums, 6));
        fl.printArray(fl.searchRange(nums, 5));
    }

    public int[] searchRange(int[] nums, int target) {
        int[] sol = new int[2];
        sol[0] = findLeft(nums,target);
        sol[1] = findRight(nums, target);
        return sol;
    }


    public  void printArray(int[] nums) {
        for (int n : nums)
            System.out.print(n + " ");
        System.out.println();
    }

    public int findLeft(int[] nums, int target) {
        int index = -1;
        int left = 0;
        int right = nums.length-1;
        int mid = (left + right)/2;
        while (left <= right) {
            if (nums[mid] == target)
                index = mid;
            if (target <= nums[mid]) {
                right = mid  - 1;
                mid = (left + right)/2;
            } else { // nums[mid] < target
                left = mid + 1;
                mid = (left+right)/2;
            }
        }

        return index;
    }

    public int findRight(int[] nums, int target) {
        int index = -1;
        int left = 0;
        int right = nums.length-1;
        int mid = (left + right)/2;
        while (left <= right) {
            if (nums[mid] == target)
                index = mid;
            if (target < nums[mid]) {
                right = mid  - 1;
                mid = (left + right)/2;
            } else { // nums[mid] <= target
                left = mid + 1;
                mid = (left+right)/2;
            }
        }

        return index;
    }
}