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(logn).

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

思路分析

这道题的input是一个升序的有序数组，然后在这个数组中查找target value的index。那么基本上就是binary search的思路，而且题目中要求时间复杂度为O(logn)，就基本确认了就是要求用binary search的算法。那么如何得到这个target value在数组中的index的range呢？一个思路就是使用两次binary search，第一次得到这个target value的most left index，第二次得到这个target value的most right index。

这道题在实现的时候要注意的是mid index的边界问题，left=0, right=len(nums)-1. right pointer不能设置为len(nums)

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums: return [-1, -1]
        left, right = 0, len(nums)-1
        result = []
        while left <= right:
            mid = left + (right-left)/2
            if nums[mid] >= target: right = mid - 1
            else: left = mid + 1
        if left >= len(nums) or nums[left] != target: return [-1, -1]
        result.append(left)
        left, right = 0, len(nums)-1
        while left <= right:
            mid = left + (right-left)/2
            if nums[mid] <= target: left = mid + 1
            else: right = mid - 1
        result.append(right)
        return result