Leetcode: Search for a range

Search for a Range | LeetCode OJ

We have a sorted array as input and we need to search for occurrences of an element. Search in a sorted array can be easily done using binary search. We need to modify the search slightly to fit our purpose.

1. Implement a search which would give the last index of element being searched
2. Call the above method twice for given target and target-1
3. Handle case where target is not present and cases where target is at either end of the array

Remarks:

1. O(log n) time complexity for using the binary search
2. O(n) space complexity as 2 copies of arrays are created for each call to the binary search function

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        p = self.get_insert_index(nums, target)
        if nums[p] != target:
            return -1, -1
        q = self.get_insert_index(nums, target - 1)
        if q < len(nums) - 1 and nums[q] != target:
            q = q + 1
        return q, p
    def get_insert_index(self, nums, target):
        lo, hi = 0, len(nums)
        mid = (lo + hi) / 2
        while mid != lo:
            if nums[mid] == target and (mid == len(nums) - 1 or nums[mid + 1] > target):
                return mid
            elif nums[mid] <= target:
                lo = mid
            else:
                hi = mid
            mid = (lo + hi) / 2
        return mid