Algorithm Day66 - Find First and Last Position of Element in Sorted Array

Posted on In , Views:

🧩 Problem Description

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If the target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

💬 Examples

Example 1

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

Example 2

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

Example 3

1
2
Input: nums = [], target = 0
Output: [-1,-1]

💡 Intuition

Since the array is sorted, we can use binary search to find:

  • The leftmost index of the target.
  • The rightmost index of the target.

This avoids scanning linearly and ensures O(log n) complexity. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = findBound(nums, target, true);
        int right = findBound(nums, target, false);
        return new int[]{left, right};
    }

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

⏱ Complexity Analysis

  • Time: O(log n) — two binary searches.
  • Space: O(1) — constant extra space.

✍️ Summary

  • Use two binary searches to find the first and last occurrence.
  • If target not found, return [-1, -1].

Related problems

  • lc-35 — Search Insert Position
  • lc-704 — Binary Search