 # LeetCode Find First and Last Position of Element in Sorted Array Solution

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`

## Solution

We want to find two positions, `first_pos` and `last_pos` of the `target` in `nums`.

For the `first_pos`, we want to find the leftmost `target`. So we will do binary search on `nums`, and whenever we find `target`, we search for its left side to see whether there is another `target` on the left while keeping track of the leftmost seen `first_pos`.

Similarly, we want to find the rightmost `target` in `nums` to be `last_pos`. So when we see a `target`, we search for its right side and record the `last_pos = current index`. If the current element is not `target`, then ordinary binary search will lead us to the correct searching side.

``````1def searchRange(self, nums, target):
2    left, right = 0, len(nums)-1
3    first_pos, last_pos = -1, -1
4
5    # find first pos
6    while left <= right:
7      mid = (left + right) // 2
8      if nums[mid] == target:
9          first_pos = mid
10          right = mid - 1
11      elif nums[mid] > target:
12          right = mid - 1
13      else:
14          left = mid + 1
15
16    #find last pos
17    left, right = 0, len(nums)-1
18    while left <= right:
19      mid = (left + right) // 2
20      if nums[mid] == target:
21          last_pos = mid
22          left = mid+1
23      elif nums[mid] > target:
24          right = mid - 1
25      else:
26          left = mid + 1
27    return (first_pos, last_pos)``````