034.md

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

Solution 1 (O(log(n)))

# Binary search
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        ans = []
        # search for starting position
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if (target == nums[mid] and
                    (mid == 0 or target != nums[mid - 1])):
                ans.append(mid)
                break
            elif target <= nums[mid]:
                r = mid - 1
            else:
                l = mid + 1
        if not ans:
            return [-1, -1]
        # search for ending position
        l, r = ans[0], len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if (target == nums[mid] and
                    (mid == len(nums) - 1 or target != nums[mid + 1])):
                ans.append(mid)
                break
            elif target < nums[mid]:
                r = mid - 1
            else:
                l = mid + 1
        return ans