## DEV Community

Abhishek Chaudhary

Posted on

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

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:

``````class Solution:
def search(self, nums, target, cmp, ncmp):
beg = 0
end = len(nums)
while beg <= end:
mid = (beg + end) // 2
if mid >= len(nums):
break
curr = nums[mid]
prev = nums[mid - 1] if mid > 0 else curr - 1
forw = nums[mid + 1] if mid < len(nums) - 1 else curr + 1
if curr == target and cmp(prev, forw):
return mid
elif beg == end:
break
elif ncmp(curr):
beg = mid + 1
else:
end = mid
return -1

def searchRange(self, nums: List[int], target: int) -> List[int]:
return [
self.search(nums, target, lambda p, f: p < target, lambda c: c < target),
self.search(nums, target, lambda p, f: f > target, lambda c: c <= target)
]
``````