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

[Link] https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Because the array is sorted, two binary searches can find the boundaries. The first search finds the first index whose value is at least target; the second finds the first index whose value is greater than target. If the first boundary is at the end of the array or does not contain target, the target is absent. Otherwise, the answer is the first boundary and one less than the second boundary. Searching for a value greater than target directly avoids computing target + 1, which could overflow for Integer.MAX_VALUE.

The loop invariant is that the boundary being sought remains in the half-open interval [left, right). Each iteration discards at least half of the remaining indices, so both searches take O(log N) time. They use O(1) extra space.

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = lowerBound(nums, target);
        if (left == nums.length || nums[left] != target) {
            return new int[] {-1, -1};
        }
        int right = upperBound(nums, target);
        return new int[] {left, right - 1};
    }

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

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