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)
        ]