Find First and Last Position of Element in Sorted Array

Problem Statement

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.

What to notice first

• Use two binary searches: one to find the leftmost occurrence, one to find the rightmost.
• When target is found, continue searching left for the first position, and continue searching right for the last position.
• The two-search pattern is a powerful technique for range queries on sorted arrays.

Examples

Input	Target	Output	Explanation
[5, 7, 7, 8, 8, 10]	8	[3, 4]	First 8 at index 3, last 8 at index 4
[5, 7, 7, 8, 8, 10]	6	[-1, -1]	Target not in array
[]	0	[-1, -1]	Empty array
[1]	1	[0, 0]	Single element matches target

Constraints

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums is a non-decreasing array
• -10^9 <= target <= 10^9

Real-World Applications

Where this pattern appears

• Database range queries — finding first and last matching records in an index.
• Time-series data — locating events within a specific time window.
• Version control — finding the range of commits with a specific tag or status.
• Log analysis — identifying the span of entries matching a condition.

Complexity Comparison

Approach	Time	Space	Best When
Binary Search	O(log n)	O(1)	Standard approach, O(log n) required
Linear Search	O(n)	O(1)	Very small arrays or exact match scenarios

Which approach should you learn first?

• Pick Binary Search to meet the O(log n) constraint and learn the two-search pattern.
• Pick Linear Search to understand the problem conceptually.

Required Time

Binary Search

O(log n) time · O(1) space

Simplicity

Linear Search

O(n) time · O(1) space

Approach 1: Binary Search (Recommended)

★ Recommended

Perform two binary searches: one to find the leftmost position by continuing left when target is found, and one to find the rightmost position by continuing right when target is found.

⏱ Time O(log n) Two binary searches 💾 Space O(1) Only pointers

Step-by-step Example

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

First search (find leftmost 8):

Step	left	right	mid	nums[mid]	Action
1	0	5	2	7	< 8 → left = 3
2	3	5	4	8	== 8 → right = 3
3	3	3	3	8	== 8 → right = 2
4	3	2	—	—	first = 3

Second search (find rightmost 8):

Step	left	right	mid	nums[mid]	Action
1	0	5	2	7	< 8 → left = 3
2	3	5	4	8	== 8 → left = 5
3	5	5	5	10	> 8 → right = 4
4	5	4	—	—	last = 4

Result: [3, 4] ✓

Pseudocode

function searchRange(nums, target):
    // Find first position
    left, right = 0, len(nums) - 1
    first = -1
    while left <= right:
        mid = left + (right - left) / 2
        if nums[mid] == target:
            first = mid
            right = mid - 1  // Continue searching left
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    if first == -1:
        return [-1, -1]

    // Find last position
    left, right = 0, len(nums) - 1
    last = -1
    while left <= right:
        mid = left + (right - left) / 2
        if nums[mid] == target:
            last = mid
            left = mid + 1  // Continue searching right
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return [first, last]

Solution Code

Python

find_first_last_position_binary_search.py

"""
#34 Find First and Last Position of Element in Sorted Array - Binary Search
Time: O(log n), Space: O(1)

Find the starting and ending position of a given target value in a sorted array.
Use two binary searches: one to find first position, one to find last.
"""


class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        """
        Two binary searches to find first and last positions.
        """
        if not nums:
            return [-1, -1]

        # Find first position
        left, right = 0, len(nums) - 1
        first_pos = -1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                first_pos = mid
                right = mid - 1  # Continue searching left
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        # If target not found
        if first_pos == -1:
            return [-1, -1]

        # Find last position
        left, right = 0, len(nums) - 1
        last_pos = -1

        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                last_pos = mid
                left = mid + 1  # Continue searching right
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return [first_pos, last_pos]


# Test cases
if __name__ == "__main__":
    sol = Solution()

    assert sol.searchRange([5, 7, 7, 8, 8, 10], 8) == [3, 4]
    assert sol.searchRange([5, 7, 7, 8, 8, 10], 6) == [-1, -1]
    assert sol.searchRange([], 0) == [-1, -1]
    assert sol.searchRange([1], 1) == [0, 0]
    assert sol.searchRange([1, 3], 3) == [1, 1]

    print("All test cases passed!")

C++

find_first_last_position_binary_search.cpp

#include <vector>
using namespace std;

/*
#34 Find First and Last Position of Element in Sorted Array - Binary Search
Time: O(log n), Space: O(1)

Find the starting and ending position of a given target value in a sorted array.
Use two binary searches: one to find first position, one to find last.
*/

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        /*
        Two binary searches to find first and last positions.
        */
        if (nums.empty()) {
            return {-1, -1};
        }

        // Find first position
        int left = 0, right = nums.size() - 1;
        int first_pos = -1;

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

        // If target not found
        if (first_pos == -1) {
            return {-1, -1};
        }

        // Find last position
        left = 0;
        right = nums.size() - 1;
        int last_pos = -1;

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

        return {first_pos, last_pos};
    }
};

Java

FindFirstLastPositionBinarySearch.java

/*
#34 Find First and Last Position of Element in Sorted Array - Binary Search
Time: O(log n), Space: O(1)

Find the starting and ending position of a given target value in a sorted array.
Use two binary searches: one to find first position, one to find last.
*/

class Solution {
    public int[] searchRange(int[] nums, int target) {
        /*
        Two binary searches to find first and last positions.
        */
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }

        // Find first position
        int left = 0, right = nums.length - 1;
        int firstPos = -1;

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

        // If target not found
        if (firstPos == -1) {
            return new int[]{-1, -1};
        }

        // Find last position
        left = 0;
        right = nums.length - 1;
        int lastPos = -1;

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

        return new int[]{firstPos, lastPos};
    }
}

JavaScript

find_first_last_position_binary_search.js

/**
 * #34 Find First and Last Position of Element in Sorted Array - Binary Search
 * Time: O(log n), Space: O(1)
 *
 * Find the starting and ending position of a given target value in a sorted array.
 * Use two binary searches: one to find first position, one to find last.
 */

class Solution {
    searchRange(nums, target) {
        /**
         * Two binary searches to find first and last positions.
         */
        if (nums.length === 0) {
            return [-1, -1];
        }

        // Find first position
        let left = 0, right = nums.length - 1;
        let firstPos = -1;

        while (left <= right) {
            const mid = left + Math.floor((right - left) / 2);
            if (nums[mid] === target) {
                firstPos = mid;
                right = mid - 1;  // Continue searching left
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // If target not found
        if (firstPos === -1) {
            return [-1, -1];
        }

        // Find last position
        left = 0;
        right = nums.length - 1;
        let lastPos = -1;

        while (left <= right) {
            const mid = left + Math.floor((right - left) / 2);
            if (nums[mid] === target) {
                lastPos = mid;
                left = mid + 1;  // Continue searching right
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return [firstPos, lastPos];
    }
}

// Export for CommonJS
module.exports = Solution;

Rust

find_first_last_position_binary_search.rs

/*
#34 Find First and Last Position of Element in Sorted Array - Binary Search
Time: O(log n), Space: O(1)

Find the starting and ending position of a given target value in a sorted array.
Use two binary searches: one to find first position, one to find last.
*/

impl Solution {
    pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
        /*
        Two binary searches to find first and last positions.
        */
        if nums.is_empty() {
            return vec![-1, -1];
        }

        // Find first position
        let mut left = 0i32;
        let mut right = nums.len() as i32 - 1;
        let mut first_pos = -1;

        while left <= right {
            let mid = (left + (right - left) / 2) as usize;
            if nums[mid] == target {
                first_pos = mid as i32;
                right = mid as i32 - 1;  // Continue searching left
            } else if nums[mid] < target {
                left = mid as i32 + 1;
            } else {
                right = mid as i32 - 1;
            }
        }

        // If target not found
        if first_pos == -1 {
            return vec![-1, -1];
        }

        // Find last position
        left = 0;
        right = nums.len() as i32 - 1;
        let mut last_pos = -1;

        while left <= right {
            let mid = (left + (right - left) / 2) as usize;
            if nums[mid] == target {
                last_pos = mid as i32;
                left = mid as i32 + 1;  // Continue searching right
            } else if nums[mid] < target {
                left = mid as i32 + 1;
            } else {
                right = mid as i32 - 1;
            }
        }

        vec![first_pos, last_pos]
    }
}

Go

find_first_last_position_binary_search.go

package main

/*
#34 Find First and Last Position of Element in Sorted Array - Binary Search
Time: O(log n), Space: O(1)

Find the starting and ending position of a given target value in a sorted array.
Use two binary searches: one to find first position, one to find last.
*/

func SearchRangeBinarySearch(nums []int, target int) []int {
  /*
  Two binary searches to find first and last positions.
  */
  if len(nums) == 0 {
    return []int{-1, -1}
  }

  // Find first position
  left, right := 0, len(nums)-1
  firstPos := -1

  for left <= right {
    mid := left + (right-left)/2
    if nums[mid] == target {
      firstPos = mid
      right = mid - 1  // Continue searching left
    } else if nums[mid] < target {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  // If target not found
  if firstPos == -1 {
    return []int{-1, -1}
  }

  // Find last position
  left = 0
  right = len(nums) - 1
  lastPos := -1

  for left <= right {
    mid := left + (right-left)/2
    if nums[mid] == target {
      lastPos = mid
      left = mid + 1  // Continue searching right
    } else if nums[mid] < target {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }

  return []int{firstPos, lastPos}
}

Approach 2: Linear Search

✓ Simple

Iterate from the start to find the first occurrence, then iterate from the end to find the last occurrence. If the target is not found during the first pass, return [-1, -1].

⏱ Time O(n) Two passes 💾 Space O(1) Only pointers

Step-by-step Example

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

First pass (find first 8):

i	nums[i]	Match?	Action
0	5	No	Continue
1	7	No	Continue
2	7	No	Continue
3	8	Yes	first = 3, break

Second pass (find last 8):

i	nums[i]	Match?	Action
5	10	No	Continue
4	8	Yes	last = 4, break

Result: [3, 4] ✓

Pseudocode

function searchRange(nums, target):
    if len(nums) == 0:
        return [-1, -1]

    first = -1
    for i in range(len(nums)):
        if nums[i] == target:
            first = i
            break

    if first == -1:
        return [-1, -1]

    last = -1
    for i in range(len(nums) - 1, -1, -1):
        if nums[i] == target:
            last = i
            break

    return [first, last]

Solution Code

Python

find_first_last_position_linear_search.py

"""
#34 Find First and Last Position of Element in Sorted Array - Linear Search
Time: O(n), Space: O(1)

Linear scan to find first and last occurrences of target value.
"""


class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        """
        Linear search to find first and last positions.
        """
        if not nums:
            return [-1, -1]

        first_pos = -1
        last_pos = -1

        # Find first position
        for i in range(len(nums)):
            if nums[i] == target:
                first_pos = i
                break

        # If target not found
        if first_pos == -1:
            return [-1, -1]

        # Find last position
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] == target:
                last_pos = i
                break

        return [first_pos, last_pos]


# Test cases
if __name__ == "__main__":
    sol = Solution()

    assert sol.searchRange([5, 7, 7, 8, 8, 10], 8) == [3, 4]
    assert sol.searchRange([5, 7, 7, 8, 8, 10], 6) == [-1, -1]
    assert sol.searchRange([], 0) == [-1, -1]
    assert sol.searchRange([1], 1) == [0, 0]
    assert sol.searchRange([1, 3], 3) == [1, 1]

    print("All test cases passed!")

C++

find_first_last_position_linear_search.cpp

#include <vector>
using namespace std;

/*
#34 Find First and Last Position of Element in Sorted Array - Linear Search
Time: O(n), Space: O(1)

Linear scan to find first and last occurrences of target value.
*/

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        /*
        Linear search to find first and last positions.
        */
        if (nums.empty()) {
            return {-1, -1};
        }

        int first_pos = -1;
        int last_pos = -1;

        // Find first position
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == target) {
                first_pos = i;
                break;
            }
        }

        // If target not found
        if (first_pos == -1) {
            return {-1, -1};
        }

        // Find last position
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (nums[i] == target) {
                last_pos = i;
                break;
            }
        }

        return {first_pos, last_pos};
    }
};

Java

FindFirstLastPositionLinearSearch.java

/*
#34 Find First and Last Position of Element in Sorted Array - Linear Search
Time: O(n), Space: O(1)

Linear scan to find first and last occurrences of target value.
*/

class Solution {
    public int[] searchRange(int[] nums, int target) {
        /*
        Linear search to find first and last positions.
        */
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }

        int firstPos = -1;
        int lastPos = -1;

        // Find first position
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                firstPos = i;
                break;
            }
        }

        // If target not found
        if (firstPos == -1) {
            return new int[]{-1, -1};
        }

        // Find last position
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] == target) {
                lastPos = i;
                break;
            }
        }

        return new int[]{firstPos, lastPos};
    }
}

JavaScript

find_first_last_position_linear_search.js

/**
 * #34 Find First and Last Position of Element in Sorted Array - Linear Search
 * Time: O(n), Space: O(1)
 *
 * Linear scan to find first and last occurrences of target value.
 */

class Solution {
    searchRange(nums, target) {
        /**
         * Linear search to find first and last positions.
         */
        if (nums.length === 0) {
            return [-1, -1];
        }

        let firstPos = -1;
        let lastPos = -1;

        // Find first position
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] === target) {
                firstPos = i;
                break;
            }
        }

        // If target not found
        if (firstPos === -1) {
            return [-1, -1];
        }

        // Find last position
        for (let i = nums.length - 1; i >= 0; i--) {
            if (nums[i] === target) {
                lastPos = i;
                break;
            }
        }

        return [firstPos, lastPos];
    }
}

// Export for CommonJS
module.exports = Solution;

Rust

find_first_last_position_linear_search.rs

/*
#34 Find First and Last Position of Element in Sorted Array - Linear Search
Time: O(n), Space: O(1)

Linear scan to find first and last occurrences of target value.
*/

impl Solution {
    pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
        /*
        Linear search to find first and last positions.
        */
        if nums.is_empty() {
            return vec![-1, -1];
        }

        let mut first_pos = -1;
        let mut last_pos = -1;

        // Find first position
        for (i, &num) in nums.iter().enumerate() {
            if num == target {
                first_pos = i as i32;
                break;
            }
        }

        // If target not found
        if first_pos == -1 {
            return vec![-1, -1];
        }

        // Find last position
        for (i, &num) in nums.iter().enumerate().rev() {
            if num == target {
                last_pos = i as i32;
                break;
            }
        }

        vec![first_pos, last_pos]
    }
}

Go

find_first_last_position_linear_search.go

package main

/*
#34 Find First and Last Position of Element in Sorted Array - Linear Search
Time: O(n), Space: O(1)

Linear scan to find first and last occurrences of target value.
*/

func SearchRangeLinearSearch(nums []int, target int) []int {
  /*
  Linear search to find first and last positions.
  */
  if len(nums) == 0 {
    return []int{-1, -1}
  }

  firstPos := -1
  lastPos := -1

  // Find first position
  for i := 0; i < len(nums); i++ {
    if nums[i] == target {
      firstPos = i
      break
    }
  }

  // If target not found
  if firstPos == -1 {
    return []int{-1, -1}
  }

  // Find last position
  for i := len(nums) - 1; i >= 0; i-- {
    if nums[i] == target {
      lastPos = i
      break
    }
  }

  return []int{firstPos, lastPos}
}

Common mistakes

Watch for these pitfalls

• Forgetting to continue the search after finding the target (instead of breaking immediately).
• Not checking if the first position is -1 before searching for the last position.
• Mixing up the direction of pointer movement in the two searches (left for first, right for last).

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

find_first_and_last_position_of_element_in_sorted_array_space_optimized.py

"""
Solution for Find First and Last Position of Element in Sorted Array
"""

def solve():
    """Implementation for approach 3 of Find First and Last Position of Element in Sorted Array"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

find_first_and_last_position_of_element_in_sorted_array_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Find First and Last Position of Element in Sorted Array
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

FindFirstAndLastPositionOfElementInSortedArraySpaceOptimized.java

/**
 * Solution for Find First and Last Position of Element in Sorted Array
 * Approach 3
 */
public class FindFirstAndLastPositionOfElementInSortedArraySpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

find_first_and_last_position_of_element_in_sorted_array_space_optimized.js

/**
 * Solution for Find First and Last Position of Element in Sorted Array
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

find_first_and_last_position_of_element_in_sorted_array_space_optimized.rs

/// Solution for Find First and Last Position of Element in Sorted Array
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

find_first_and_last_position_of_element_in_sorted_array_space_optimized.go

package main

import "fmt"

// Solution for Find First and Last Position of Element in Sorted Array
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Binary Search ↗ Easy #704
• Search Insert Position ↗ Easy #35
• Search in Rotated Sorted Array ↗ Medium #33
• Find Peak Element ↗ Medium #162

Interview Tips

Key trade-offs to discuss

• Why two searches? Finding first and last requires different logic: continue left for first, continue right for last.
• Early termination: If the first search returns -1, no need to search for the last.
• Efficiency: Binary search is crucial here. Linear would be O(n) but two binary searches give O(log n).
• Edge cases: Empty array, single element, target at boundaries, arrays with all same values (within constraints).

← Previous
#33 Search in Rotated Sorted Array Next
#35 Search Insert Position →