# Leetcode 34. 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 `target`

is not found in the array, return `[-1, -1]`

.

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

runtime complexity.

# Test Cases

**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]

**Constraints**

`0 <= nums.length <= 10^5`

`-10^9 <= nums[i] <= 10^9`

`nums`

is a non-decreasing array.`-10^9 <= target <= 10^9`

# Approach

We need to search for a **target **inside the given sorted array and need to track the first and last occurrence of that **target.**

We can normally do a linear search on the given array and search for that **target. **Track the first and last occurrence and just store them. Here our time complexity will be **O(n) where n = length of array.**

But can’t we make use of the fact that the array is sorted. If the array is sorted and our mission is something related to searching inside the array and track something, we can always go for binary search.

We need to track the **left most **target and **right most** target. So we need 2 binary search on the given array.

- One binary search will search for the target + we try to find the left most occurrence of that target.
- Another binary search will again do the search for the target + we try to find the right most occurrence of that target.

private int findLeftMost(int [] nums, int target) {

int length = nums.length;

int low = 0;

int high = length - 1;

int index = -1;

while (low <= high) {

int middle = low + (high - low) / 2;

if (nums[middle] == target) {

index = middle;

high = middle - 1;

}

else if (nums[middle] < target){

low = middle + 1;

}

else {

high = middle - 1;

}

}

return index;

}private int findRightMost(int [] nums, int target) {

int length = nums.length;

int low = 0;

int high = length - 1;

int index = -1;

while (low <= high) {

int middle = low + (high - low) / 2;

if (nums[middle] == target) {

index = middle;

low = middle + 1;

}

else if (nums[middle] > target){

high = middle - 1;

}

else {

low = middle + 1;

}

}

return index;

}

These are the two binary search that will come in handy. So what basically happens here.

In the first binary search, we are returning the index where the target occurs the very first time. If we sees the target, we move our **right pointer to middle — 1 as the first occurrence of that target will be towards the left most area.**

In the second binary search, we are returning the index where the target occurs the very last time. If we sees the target, we move our **left pointer to middle +1 as the last occurrence of that target will be towards the right most area.**

## Algorithm

- Check whether the given array is empty or not.(Edge case).
- Do the first binary search to find the left most index.
- If it is -1, then that target is not present, return {-1, -1}.
- Otherwise, do the second binary search to find the right most index.
- Return {leftMostIndex, rightMostIndex}.

# Time Complexity

Here we are doing binary search 2 times.The time complexity will be**O(logn) + O(logn) where n = length of array.**

We are not making use of any extra space, so space complexity will be O(1).