# Find First and Last Position of Element in Sorted Array

Published: Dec 12, 2022

Medium Binary Search

## Problem Description

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

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

Constraints:

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

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

## Examples

``````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]
``````
``````Example 3
Input: nums = [], target = 0
Output: [-1,-1]
``````

## How to Solve

The problem asks O(log(n)) time complexity. This means we should use the binary search. Python and C++ have convenient binary search features in the standard library. When the left bound is found:

• check the left bound is not the last position since such position means the given array might be empty
• check the value at left bound is the target, unless the target does not exist in the given array.

If the left bound is good, find the right bound and return the result.

## Solution

``````class FindFirstAndLastPositionOfElementInSortedArray {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int left = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
if (left == nums.size() || nums[left] != target) { return {-1, -1}; }
int right = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
return {left, right};
}
};
``````
``````
``````
``````
``````
``````class FindFirstAndLastPositionOfElementInSortedArray:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left = bisect.bisect_left(nums, target)
if left == len(nums) or nums[left] != target: return [-1, -1]
right = bisect.bisect_right(nums, target) - 1
return [left, right]
``````
``````
``````

## Complexities

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