34.md

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

my thoughts:

1. binary search for starting target, if not found return [-1,-1]; if found binary search between starting target and the end.

my solution:

**********40 ms
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums:
            return [-1, -1]
        l, r = 0, len(nums)-1
        res = [-1, -1]
        while l<=r:
            m = (l+r)/2
            #print l,m,r
            if nums[m] == target:
                if m == 0 or nums[m-1] < target:
                    res[0] = m
                    break
                else:
                    r = m-1
            elif nums[m] < target:
                l = m+1
            else:
                r = m-1
                
        if res[0] == -1:
            return res
        
        l = res[0]
        r = len(nums) - 1
        while l<=r:
            m = (l+r)/2
            if nums[m] == target:
                if m == len(nums)-1 or nums[m+1] > target:
                    res[1] = m
                    return res
                else:
                    l = m+1
            elif nums[m] < target:
                l = m+1
            else:
                r = m-1

my comments:

from other ppl's solution:

1. interesting recursion, 32ms:
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums: return [-1,-1]
        n = len(nums)
        return self.helper(nums,0,n-1,target)
        
    def helper(self,nums,lo,hi,target):
        if nums[lo] == nums[hi] == target:
            return [lo,hi]
        
        if nums[lo] > target or nums[hi] < target:
            return [-1,-1]
        
        mid = (lo+hi)/2
        l = self.helper(nums,lo,mid,target)
        r = self.helper(nums,mid+1,hi,target)
        
        if l == [-1,-1]: return r
        if r == [-1,-1]: return l
        
        return [l[0],r[1]]