Course4all
Join us on telegram
Home/dsa/Binary Search/Find First and Last Position of Element in Sorted Array

Find First and Last Position of Element in Sorted Array

Master this topic with zero to advance depth.

Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If target is not found in the array, return [-1, -1]. You must write an algorithm with O(logN)O(\\log N) runtime complexity.

Medium

Examples

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

Level I: Brute Force (Two Pass Linear Scan)

Intuition

Scan from the left to find the first occurrence, and from the right to find the last. While simple, it takes O(N)O(N) time, missing the efficiency of sorted bounds.

⏱ $O(N)$💾 $O(1)$

Detailed Dry Run

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

  • First: index 0(5), 1(7), 2(7), 3(8) -> 3
  • Last: index 5(10), 4(8) -> 4 Result: [3, 4]
java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = -1, last = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                if (first == -1) first = i;
                last = i;
            }
        }
        return new int[]{first, last};
    }
}
Approach 2

Level II: Optimal (Built-in Library)

Intuition

Most languages provide built-in binary search functions (like bisect_left and bisect_right in Python, or lower_bound/upper_bound in C++). These are highly optimized and should be used in production.

⏱ $O(\log N)$💾 $O(1)$

Detailed Dry Run

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

  1. lower_bound finds first index where val >= 8: index 3.
  2. upper_bound finds first index where val > 8: index 5.
  3. Result: [3, 5-1=4].
java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = lowerBound(nums, target);
        if (start == nums.length || nums[start] != target) return new int[]{-1, -1};
        int end = lowerBound(nums, target + 1) - 1;
        return new int[]{start, end};
    }
    private int lowerBound(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < target) l = mid + 1; else r = mid;
        }
        return l;
    }
}
Approach 3

Level III: Optimal (Two Binary Searches)

Intuition

We perform two separate binary searches. In the first search (find left bound), when nums[mid] == target, we continue searching left (high = mid - 1). In the second search (find right bound), we continue searching right (low = mid + 1).

⏱ $O(\\log N)$💾 $O(1)$

Detailed Dry Run

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

  1. Search First: mid = 2 (val 7). 7 < 8 -> L=3. mid = 4 (val 8). 8==8 -> save 4, R=3. mid = 3 (val 8). 8==8 -> save 3, R=2. End. Result index 3.
  2. Search Last: Similar logic searching right. Result index 4.
java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = findBound(nums, target, true);
        if (first == -1) return new int[]{-1, -1};
        int last = findBound(nums, target, false);
        return new int[]{first, last};
    }
    private int findBound(int[] nums, int target, boolean isFirst) {
        int l = 0, r = nums.length - 1, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                ans = mid;
                if (isFirst) r = mid - 1;
                else l = mid + 1;
            } else if (nums[mid] < target) l = mid + 1;
            else r = mid - 1;
        }
        return ans;
    }
}
← Previous QuestionSearch Insert Position
Next Question →Find Peak Element