34. Search for a Range

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of $O(\log{n})$.

If the target is not found in the array, return [-1, -1].

For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

Solution: Binary Search

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        def binary_search(low, high):
            if low > high:
                return [-1, -1]
            mid = low + (high - low) / 2
            if nums[mid] == target:
                left = binary_search(low, mid - 1)[0]
                right = binary_search(mid + 1, high)[1]
                if left == -1:
                    left = mid
                if right == -1:
                    right = mid
                return [left, right]
            if nums[mid] < target:
                return binary_search(mid + 1, high)
            return binary_search(low, mid - 1)

        return binary_search(0, len(nums) - 1)