# 34. Find First and Last Position of Element in Sorted Array

### Description

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

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

**Follow up:** Could you write an algorithm with `O(log n)` runtime complexity?

### Constraints

* `0 <= nums.length <= 105`
* `-109 <= nums[i] <= 109`
* `nums` is a non-decreasing array.
* `-109 <= target <= 109`

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/)
* [ProgramCreek](https://www.programcreek.com/2014/04/leetcode-search-for-a-range-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** nums = \[5, 7, 7, 8, 8, 10], target = 8

**Output:** \[3, 4]
{% endtab %}

{% tab title="Example 2" %}
**Input:** nums = \[5, 7, 7, 8, 8, 10], target = 6

**Output:** \[-1, -1]
{% endtab %}

{% tab title="Example 3" %}
**Input:** nums = \[], target = 0

**Output:** \[-1, -1]
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};
        if(nums == null || nums.length == 0) return result;
        int index = binarySearch(nums, target, 0, nums.length-1);
        if(index == -1) return result;
        result[0] = index;
        result[1] = index;
        int i = index;
        while(i > 0 && nums[i-1] == target) {
            i = binarySearch(nums, target, 0, i-1);
            if(result[0] == i) break;
            if(i != -1) result[0] = i;
        }
        i = index;
        while(i < nums.length-1 && nums[i+1] == target) {
            i = binarySearch(nums, target, i+1, nums.length);
            if(result[1] == i) break;
            if(i != -1) result[1] = i;
        }
        return result;
    }
    
    private int binarySearch(int[] nums, int target, int low, int high) {
        while(low <= high) {
            int mid = (low+high)/2;
            if(nums[mid] == target) {
                return mid;
            }
            if(nums[mid] < target) {
                low = mid+1;
            } else {
                high = mid-1;
            }
        }
        return -1;
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        if(nums == null || nums.length == 0) {
            return result;
        }
        
        int n = nums.length;
        int index = binarySearch(nums, target, 0, n-1);
        
        if(index >= 0) {        
            int lower = index;
            while(lower > 0 && nums[lower-1] == target) {
                int tmpIdx = binarySearch(nums, target, 0, lower-1);
                if(tmpIdx >= 0) {
                    lower = tmpIdx;
                } else {
                    break;
                }
            }
            result[0] = lower;

            int higher = index;
            while(higher < n-1 && nums[higher+1] == target) {
                int tmpIdx = binarySearch(nums, target, higher+1, n-1);
                if(tmpIdx >= 0) {
                    higher = tmpIdx;
                } else {
                    break;
                }
            }
            
            result[1] = higher;
        }
        
        return result;
    }
    
    private int binarySearch(int[] nums, int target, int low, int high) {
        while(low <= high) {
            int mid = low + (high-low)/2;
            if(nums[mid] == target) {
                return mid;
            }
            if(nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/find-first-and-last-position-of-element-in-sorted-array.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.