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

解：

Search for a range 的题目可以拆解为找 first & last position 的题目，即要做两次二分

使用改进的二分查找法。终止条件是：left + 1 < right 这样结束的时候，会有2个值供我们判断。这样做的最大的好处是，不用处理各种越界问题。

1. 先找左边界。当mid == target,将right移动到mid，继续查找左边界。

   最后如果没有找到target,退出

2. 再找右边界。当mid == target,将left移动到mid，继续查找右边界。

   最后如果没有找到target,退出

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(nums) == 0:
            return [-1,-1]
        result = [-1,-1]
        # 寻找左边界
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = (start+end)/2
            if target > nums[mid]:
                start = mid
            # target<=nums[mid] 如果相等，继续往左寻找左边界
            else:
                end = mid
        if nums[start] == target:
            result[0] = start
        elif nums[end] == target:
            result[0] = end
        else:
            return result

        # 寻找右边界
        start, end = 0, len(nums) - 1
        while start + 1 < end:
            mid = (start+end)/2
            # 如果相等，继续往右寻找右边界
            if target >= nums[mid]:
                start = mid
            else:
                end = mid
        if nums[end] == target:
            result[1] = end
        elif nums[start] == target:
            result[1] = start
        else:
            return result
        return result

源码分析

1. 首先对输入做异常处理，数组为空或者长度为0

2. 初始化start, end, mid三个变量，注意mid的求值方法，可以防止两个整型值相加时溢出

3. 使用迭代而不是递归进行二分查找

4. while终止条件应为start + 1 < end而不是start <= end，start == end时可能出现死循环

5. 先求左边界，迭代终止时先判断nums[start]== target，再判断nums[end]== target，因为迭代终止时target必取start或end中的一个，而end又大于start，取左边界即为start.

6. 再求右边界，迭代终止时先判断nums[end] == target，再判断nums[start] == target

7. 两次二分查找除了终止条件不同，中间逻辑也不同，即当nums[mid] == target如果是左边界（first postion），中间逻辑是end = mid；若是右边界（last position），中间逻辑是start = mid

8. 两次二分查找中间勿忘记重置start, end的变量值。