Find First and Last Position of Element in Sorted Array

Why it belongs on this sheet

This teaches you how to turn one binary search into two clean boundary searches.

Pattern

Lower bound and upper bound

Approach

Binary search once for the first index where the target could appear, then again for the first index greater than the target. The answer range is built from those two boundaries.

Java solution

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

    int last = lowerBound(nums, target + 1) - 1;
    return new int[] {first, last};
  }

  private int lowerBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;

    while (left < right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    return left;
  }
}

Complexity

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

Interview note

Thinking in terms of "first valid position" is usually more robust than ad-hoc boundary checks.