# 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
```

## 源码分析 <a href="#e6-ba-90-e7-a0-81-e5-88-86-e6-9e-90" id="e6-ba-90-e7-a0-81-e5-88-86-e6-9e-90"></a>

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`的变量值。