# Find First and Last Position of Element in Sorted Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array)
Canonical: https://scaleengineer.com/dsa/problems/find-first-and-last-position-of-element-in-sorted-array
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Atlassian](https://scaleengineer.com/companies/atlassian), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Capgemini](https://scaleengineer.com/companies/capgemini), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Tekion](https://scaleengineer.com/companies/tekion), [TikTok](https://scaleengineer.com/companies/tiktok), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [tcs](https://scaleengineer.com/companies/tcs), [Airtel](https://scaleengineer.com/companies/airtel), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Turing](https://scaleengineer.com/companies/turing), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Pinterest](https://scaleengineer.com/companies/pinterest), [Splunk](https://scaleengineer.com/companies/splunk), [Zillow](https://scaleengineer.com/companies/zillow), [NetApp](https://scaleengineer.com/companies/netapp), [Applied Intuition](https://scaleengineer.com/companies/applied-intuition), [Attentive](https://scaleengineer.com/companies/attentive), [Instacart](https://scaleengineer.com/companies/instacart)
---
## Problem
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.

**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 <= 105`
* `-109 <= nums[i] <= 109`
* `nums` is a non-decreasing array.
* `-109 <= target <= 109`

# Approaches
## Linear Scan
The most straightforward approach is to iterate through the entire array. We can use two variables, one to store the index of the first occurrence and another for the last. We traverse the array, and whenever we find the target element, we update these variables.
**Time:** O(n) · **Space:** O(1)
**Pros:** Very simple to understand and implement.
**Cons:** Inefficient for large arrays.; Time complexity of O(n) does not meet the problem's requirement of O(log n).; It doesn't leverage the fact that the input array is sorted.
### Explanation
This method involves a single pass through the array from left to right. We keep track of the first and last indices where the target element is found. The first time we encounter the target, we record its index in a variable, say `first`. For every occurrence of the target, we update another variable, `last`. If the loop completes and we never found the target, the initial values indicating 'not found' (e.g., -1) are returned.

```java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};
        // Find the first occurrence
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                result[0] = i;
                break;
            }
        }

        // If the first occurrence was not found, the element doesn't exist.
        if (result[0] == -1) {
            return result;
        }

        // Find the last occurrence, searching backwards
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] == target) {
                result[1] = i;
                break;
            }
        }

        return result;
    }
}
```
### Algorithm
*   Initialize a result array `ans` to `[-1, -1]`.
*   Iterate through the `nums` array from left to right with index `i`.
*   If `nums[i]` equals the `target`:
    *   If `ans[0]` is still `-1`, it means this is the first time we've seen the target. Set `ans[0] = i`.
    *   Always update the last seen position: `ans[1] = i`.
*   After the loop finishes, return the `ans` array.

## Binary Search to Find First and Last Occurrences
Since the array is sorted and the time complexity requirement is O(log n), binary search is the indicated approach. A standard binary search finds if an element exists, but we need its first and last positions. We can achieve this by running two modified binary searches: one to find the leftmost (first) occurrence and another to find the rightmost (last) occurrence.
**Time:** O(log n) · **Space:** O(1)
**Pros:** Optimal time complexity of O(log n), which is very efficient for large datasets.; Fully utilizes the sorted property of the array.
**Cons:** Slightly more complex to implement and reason about than a simple linear scan.; Requires careful handling of boundary conditions and loop termination in the binary searches.
### Explanation
This approach consists of two main parts: finding the first position and finding the last position of the target. Both can be found using a variation of the standard binary search algorithm. We design one search to be 'left-biased', meaning it continues to search the left part of the array even after finding the target, to ensure it finds the absolute first occurrence. The second search is 'right-biased', continuing to search the right part to find the absolute last occurrence.

```java
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = findFirst(nums, target);
        if (first == -1) {
            return new int[]{-1, -1};
        }
        int last = findLast(nums, target);
        return new int[]{first, last};
    }

    // Helper function to find the first occurrence of the target
    private int findFirst(int[] nums, int target) {
        int index = -1;
        int low = 0;
        int high = nums.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                index = mid;      // Potential answer found
                high = mid - 1;   // Continue searching on the left side
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return index;
    }

    // Helper function to find the last occurrence of the target
    private int findLast(int[] nums, int target) {
        int index = -1;
        int low = 0;
        int high = nums.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                index = mid;    // Potential answer found
                low = mid + 1;  // Continue searching on the right side
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return index;
    }
}
```
### Algorithm
*   Define a function `searchRange` that will return the final `[-1, -1]` or `[first, last]` array.
*   Inside `searchRange`, call a helper function, `findFirst`, to find the leftmost index of the `target`.
*   If `findFirst` returns `-1`, the target is not in the array, so return `[-1, -1]` immediately.
*   If the target was found, call another helper function, `findLast`, to find the rightmost index of the `target`.
*   Return the results from `findFirst` and `findLast` in an array.

**`findFirst` (Left-Biased Binary Search):**
*   Perform a binary search.
*   If `nums[mid] == target`, we've found a potential first occurrence. Store `mid` as the answer and continue searching in the left half (`high = mid - 1`) to find an even earlier one.
*   If `nums[mid] < target`, search in the right half (`low = mid + 1`).
*   If `nums[mid] > target`, search in the left half (`high = mid - 1`).

**`findLast` (Right-Biased Binary Search):**
*   Perform a binary search.
*   If `nums[mid] == target`, we've found a potential last occurrence. Store `mid` as the answer and continue searching in the right half (`low = mid + 1`) to find a later one.
*   If `nums[mid] < target`, search in the right half (`low = mid + 1`).
*   If `nums[mid] > target`, search in the left half (`high = mid - 1`).

# Solutions
### CSharp

```csharp
public class Solution {
    public int[] SearchRange(int[] nums, int target) {
        int l = Search(nums, target);
        int r = Search(nums, target + 1);
        return l == r ? new int[] {
            -1, -1
        } : new int[] {
            l,
            r - 1
        };
    }
    private int Search(int[] nums, int x) {
        int left = 0, right = nums.Length;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] >= x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}
```

### Java

```java
boolean check ( int x ) { } int search ( int left , int right ) { while ( left < right ) { int mid = ( left + right + 1 ) >> 1 ; if ( check ( mid )) { left = mid ; } else { right = mid - 1 ; } } return left ; }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var searchRange =
  function (nums, target) {
    function search(x) {
      let left = 0,
        right = nums.length;
      while (left < right) {
        const mid = (left + right) >> 1;
        if (nums[mid] >= x) {
          right = mid;
        } else {
          left = mid + 1;
        }
      }
      return left;
    }
    const l = search(target);
    const r = search(target + 1);
    return l == r ? [-1, -1] : [l, r - 1];
  };

```

### CPP

```cpp
class Solution {
public:
  vector<int> searchRange(vector<int> &nums, int target) {
    int l = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
    int r = lower_bound(nums.begin(), nums.end(), target + 1) - nums.begin();
    if (l == r)
      return {-1, -1};
    return {l, r - 1};
  }
};

```

### Python

```python
''' >>> bisect.bisect_left([1,1,1,2,2,2,7,7,7], 2) 3 >>> bisect.bisect_left([1,1,1,2,2,2,7,7,7], 2+1) 6 >>> bisect.bisect_right([1,1,1,2,2,2,7,7,7], 2) 6 >>> bisect.bisect_right([1,1,1,2,2,2,7,7,7], 2+1) 6 >>> bisect.bisect_left([1,1,1,2,2,2,7,7,7], 0) 0 >>> bisect.bisect_left([1,1,1,2,2,2,7,7,7], 1) 0 # below, even single value for 2, after +1 the index will be different >>> bisect.bisect_left([1,2,3,4,5], 2) 1 >>> bisect.bisect_left([1,2,3,4,5], 2+1) 2 ''' import bisect class Solution : def searchRange ( self , nums : List [ int ], target : int ) -> List [ int ]: l = bisect_left ( nums , target ) r = bisect_left ( nums , target + 1 ) return [ - 1 , - 1 ] if l == r else [ l , r - 1 ] ############ class Solution : def searchRange ( self , nums : List [ int ], target : int ) -> List [ int ]: def findRange ( to_left ): l , r = 0 , len ( nums ) - 1 m = 0 while l <= r : m = l + ( r - l ) // 2 if nums [ m ] < target : l = m + 1 elif nums [ m ] > target : r = m - 1 elif to_left and m > 0 and nums [ m - 1 ] == nums [ m ]: # so now nums[m] == target, but maybe not the leftmost or rightmost r = m - 1 elif not to_left and m + 1 < len ( nums ) and nums [ m + 1 ] == nums [ m ]: # so now nums[m] == target, but maybe not the leftmost or rightmost l = m + 1 else : return m if m < len ( nums ) and nums [ m ] == target : # 1. cover not-found, # or 2. cover input=[3] and target=3, first and last both 0, return [0,0] return m else : return - 1 return [ findRange ( True ), findRange ( False )]
```