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

### Leetcode

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

### 題目

\
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.

&#x20;

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

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

```
var searchRange = function(nums, target) {
    let startIndex = -1;
    let endIndex = -1;
    
    const searchLeft = (start, end) => {
        while(start < end) {
            const mid = Math.floor((start+end) / 2);
            if(target === nums[mid]) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
    const searchRight = (start, end) => {
        while(start < end) {
            const mid = Math.ceil((start+end) / 2);
            if(target === nums[mid]) {
                start = mid;
            } else {
                end = mid - 1;
            }
        }
        return start;
    }
    
    let start = 0;
    let end = nums.length - 1;
    
    while(start <= end) {
        const mid = Math.floor((start+end) / 2);
        if(target === nums[mid]) {
            // 找到 target 後，往左找出 index 最小的 target
            startIndex = searchLeft(start, mid);
            // 找到 target 後，往右找出 index 最大的 target
            endIndex = searchRight(mid, end);
            return [startIndex, endIndex];
        } else if (target > nums[mid]) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return [startIndex, endIndex];
};
```

Runtime: 103 ms, faster than 15.89% of JavaScript online submissions for Find First and Last Position of Element in Sorted Array.

Memory Usage: 39.9 MB, less than 91.37% of JavaScript online submissions for Find First and Last Position of Element in Sorted Array.

### 測資

```
let nums = [5,7,7,8,8,10], target = 8; // [3, 4]
// nums = [5,7,7,8,8,10], target = 6; // [-1,-1]
// nums = [], target = 0; // [-1,-1]

console.log(searchRange(nums, target));
```
