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

LeetCode 
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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return new int[]{-1, -1};

        int left = binarySearch(nums, 0, n - 1, target, true);
        if (left == -1) return new int[]{-1, -1};
        int right = binarySearch(nums, left, n - 1, target, false);
        return new int[]{left, right};
    }

    private int binarySearch(int[] nums, int left, int right, int target, boolean findFirst) {
        int result = -1;
        while (left <= right) {
            int pos = left + (right - left) / 2;
            if (nums[pos] == target) {
                result = pos;
                if (findFirst) {
                    right = pos - 1;
                } else {
                    left = pos + 1;
                }
            } else if (nums[pos] < target) {
                left = pos + 1;
            } else {
                right = pos - 1;
            }
        }
        return result;
    }
}

Remarks:

  1. TC: $O(\log n)$
  2. Use a flag in the binary search to find the left or right boundary
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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = findBound(nums, target, true);
        if (left == -1) return new int[]{-1, -1}; // target not found
        int right = findBound(nums, target, false);
        return new int[]{left, right};
    }

    private int findBound(int[] nums, int target, boolean isLeft) {
        int left = 0, right = nums.length - 1;
        int bound = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                bound = mid;
                // keep looking in left/right half depending on isLeft
                if (isLeft) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return bound;
    }
}