Find First and Last Position in Sorted Array

Share

Given an array of integers sorted in non-decreasing order, find the starting and ending positions of a given target. If target is not in array, return [-1, -1]. Must run in O(log n).

Example 1
Input: nums=[5,7,7,8,8,10], target=8 → Output: [3,4]
Example 2
Input: nums=[5,7,7,8,8,10], target=6 → Output: [-1,-1]

Solution Approach

Run binary search twice: once to find the leftmost position (first occurrence) and once to find the rightmost position (last occurrence).

  • findLeft: binary search where we continue searching left when nums[mid]==target.
  • findRight: binary search where we continue searching right when nums[mid]==target.
  • Combine both results.
Java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{findLeft(nums, target), findRight(nums, target)};
    }
    private int findLeft(int[] nums, int t) {
        int lo = 0, hi = nums.length - 1, res = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == t) { res = mid; hi = mid - 1; }
            else if (nums[mid] < t) lo = mid + 1;
            else hi = mid - 1;
        }
        return res;
    }
    private int findRight(int[] nums, int t) {
        int lo = 0, hi = nums.length - 1, res = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == t) { res = mid; lo = mid + 1; }
            else if (nums[mid] < t) lo = mid + 1;
            else hi = mid - 1;
        }
        return res;
    }
}
  • Time Complexity: O(log N)
  • Space Complexity: O(1)