Find First and Last Position of Element in Sorted Array

medium binary search

Problem

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1].

Inputnums = [5,7,7,8,8,10], target = 8

Output[3, 4]

Two binary searches: lower-bound finds the first ≥ target; upper-bound finds the first > target. The last index is upper − 1.

nums (sorted, comma-separated)

target

def search_range(nums, target):
    def bound(strict):
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < target or (strict and nums[mid] == target):
                lo = mid + 1
            else:
                hi = mid
        return lo
    first = bound(False)
    last = bound(True) - 1
    if first <= last: return [first, last]
    return [-1, -1]

function searchRange(nums, target) {
  function bound(strict) {
    let lo = 0, hi = nums.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (nums[mid] < target || (strict && nums[mid] === target)) lo = mid + 1;
      else hi = mid;
    }
    return lo;
  }
  const first = bound(false);
  const last = bound(true) - 1;
  return first <= last ? [first, last] : [-1, -1];
}

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = bound(nums, target, false);
        int last = bound(nums, target, true) - 1;
        return first <= last ? new int[]{first, last} : new int[]{-1, -1};
    }
    private int bound(int[] nums, int target, boolean strict) {
        int lo = 0, hi = nums.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (nums[mid] < target || (strict && nums[mid] == target)) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}

vector<int> searchRange(vector<int>& nums, int target) {
    auto bound = [&](bool strict) {
        int lo = 0, hi = (int) nums.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (nums[mid] < target || (strict && nums[mid] == target)) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    };
    int first = bound(false), last = bound(true) - 1;
    return first <= last ? vector<int>{first, last} : vector<int>{-1, -1};
}

Explanation

The clever idea here is to find the two boundaries of the target's run with two separate binary searches instead of scanning the whole array. One search finds where the target starts, the other finds where it ends.

The helper bound(strict) looks for a split point. With strict = false it finds the first index whose value is >= target (the lower bound, i.e. the first position). With strict = true it treats equal values like "too small" too, so it lands on the first index whose value is > target — and the last target sits just one step before that.

That is why last = bound(true) - 1. If the target never appears, the two bounds collapse so that first > last, and we return [-1, -1].

Example: nums = [5,7,7,8,8,10], target = 8. The lower-bound search stops at index 3 (first 8). The upper-bound search stops at index 5 (first value > 8), so the last 8 is at 5 - 1 = 4. Answer: [3, 4].

Each search halves the range every step, so the whole thing runs in O(log n) time.

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