034. Search for a Range.md

34. Search for a Range

题目：

https://leetcode.com/problems/search-for-a-range/

难度 : Medium

思路：

一开始想啊想，觉得虽然用到了二分，但都不是O(logN)

后来看到hint:

采用两次二分查找。首先二分找到第一个该值出现的位置，譬如m，然后在[m, n)区间内第二次二分找到最后一个该值出现的位置。

二分查找其实不容易写对，看到哪里写的，其实是的，有要点：

• 关于right的赋值

• • right = n-1 => while(left <= right) => right = middle-1;
  • right = n => while(left < right) => right = middle;

• middle的计算不能写在while循环外，否则无法得到更新。

  ​

AC 代码

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums : return [-1, -1]

        result = []
        l, r = 0, len(nums)

        while l < r:
            mid = (l + r) // 2
            if nums[mid] == target and (mid == 0 or nums[mid-1] != target):
                result.append(mid)
                break
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid
        if not result:
            return [-1, -1]

        l,r = 0, len(nums)
        while l < r:
            mid = ( l + r )// 2
            if nums[mid] == target and (mid == len(nums)-1 or nums[mid+1] != target):
                result.append(mid)
                break
            if nums[mid] <= target:
                l = mid + 1
            else:
                r = mid

        return result