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

Run binary search twice: once biased to keep going left after a hit (finding the first index), once biased to keep going right (finding the last). Together they bracket the target's range in O(log n).

Idea

A single binary search finds some occurrence, but we need the exact left and right boundaries. Run two boundary searches:

• First position: when nums[mid] == target, record mid but keep searching left (hi = mid - 1).
• Last position: on a hit, record mid but keep searching right (lo = mid + 1).

Each search is O(log n), and if the target never appears both return -1.

Algorithm

bound(is_first):

1. lo=0, hi=n-1, res=-1.
2. While lo <= hi: mid=(lo+hi)//2. If nums[mid]==target, set res=mid and go left (first) or right (last). If nums[mid]<target, lo=mid+1; else hi=mid-1.
3. Return res. Answer = [bound(first), bound(last)].

Worked example: nums = [5,7,7,8,8,10], target = 8

• First-search converges to index 3; last-search to index 4.

Result: [3, 4].

Complexity

• Time: O(log n).
• Space: O(1).

class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{bound(nums, target, true), bound(nums, target, false)};
    }

    private int bound(int[] nums, int target, boolean isFirst) {
        int lo = 0, hi = nums.length - 1, res = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                res = mid;
                if (isFirst) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else if (nums[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return res;
    }
}