34. 在排序数组中查找元素的第一个和最后一个位置

原题地址（中等）

方法1—一种二分查找

二分查找思路很简单，但细节是魔鬼

思路

这题一看要求时间复杂度 O(logN) ，就能立刻想到是二分查找。

这题考察的就是二分查找的细节。
**
套用模板2试一试
二分查找模板
并且使得 nums[mid]==target 时 high=mid ，即

while low < high:
      mid = low + (high - low) // 2
      if nums[mid] < target:
          low = mid + 1
      else:  
          high = mid

这个二分可以查找数组中第一个出现的 target ，
如果 target 不存在，则会返回第一个比target大的数；
如果都比 target 小，则会返回最后一个数；
如果都比 target 大，则会返回第一个数。

这样，我们就找到了第一个 target ，那么，我们怎么找到最后一个 target 呢？是否需要再想一个二分查找？
再写一个二分查找肯定能够解决，我们放到方法2，但是在这里，我们还是使用上面的二分查找。

上面的二分查找可以查找数组中第一个出现的 target ，那么肯定也可以查找数组中第一个出现的 target+1 ，这个数的前一个，不就是最后一个 **target** 吗。
**
所以运用两次相同的二分查找，就可以解决问题了。

具体细节放到代码的注释中讲解。

代码1

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        if n == 0 or nums[n-1] < target or nums[0] > target:  # 特判，直接返回
            return [-1, -1]
        low, high = 0, n-1
        # 以下循环会找出第一个target的下标
        while low < high:
            mid = low + (high - low) // 2
            if nums[mid] < target:
                low = mid + 1
            else:  
                high = mid
        if nums[low] != target:  # 如果不存在target，直接返回
            return [-1, -1]
        left = low   # 记下最左边的target的下标
        # 第二个循环，找出第一个比target大的数的下标，
        # 有一个特殊情况就是[1,2,3,3,3] target+1=4 这种情况会返回最后一个3，所以在循环结束后用一个if else做了特判
        low, high = low, n-1
        while low < high:
            mid = low + (high - low) // 2
            if nums[mid] < target+1:
                low = mid + 1
            else:  
                high = mid
        if nums[low] > target:
            right = low-1
        else:
            right = low
        return [left, right]

代码2

将两次 while 循环写成一个函数

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binarySearch(low, high, k):
            while low < high:
                mid = low + (high - low) // 2
                if nums[mid] < k:
                    low = mid + 1
                else:  
                    high = mid
            return low
        n = len(nums)
        if n == 0 or nums[n-1] < target or nums[0] > target:  # 特判，直接返回
            return [-1, -1]
        left = binarySearch(0, n-1, target)
        if nums[left] != target:  # 如果不存在target，直接返回
            return [-1, -1]
        right = binarySearch(left, n-1, target+1)
        if nums[right] > target:
            right -= 1
        return [left, right]

时空复杂度

时间复杂度：两次二分，为 O(logN)
空间复杂度： O(1)

方法2—两种二分查找

思路

方法1中我们用一个二分查找模板，分别代入 target 和 target+1 求解出了 target 和 target+1 的最左端，从而间接求出了 target 的左右端点。

在方法二中，我们用细节上有差别的两种二分查找，来搜索出左右端点。

如果看完此文还不明白的话，可以回过头来看下面文章：

方法1中的模板是无法既查找左侧区间又查找右侧区间的，那如果我们试一试模板1呢？
语雀内容
也就是说循环中有三个判断条件，而不是两个。

使用此模板的话，如果要找左侧端点，那么当 nums[mid] == target 就应该进入左侧区间；如果要找右侧端点，就应该进入右侧区间。

先来查找左侧端点：

left, right = 0, n-1
while left <= right:
    mid = left + (right - left) // 2
    if nums[mid] == target:
        right = mid - 1
    elif nums[mid] > target:
        right = mid - 1
    else:
        left = mid + 1

注意，这个代码最后退出循环时一定有 left>right 即 left == right+1 。

• 如果 nums 中存在 target ，那么最后一定会走 if nums[mid] == target: right = mid - 1 这一步，然后循环条件被破坏，循环终止，此时 nums[left] 就是 target
• 如果 nums 中不存在 target ，我们也不用考虑太多，比较麻烦。由于我们知道了如果**nums 中存在 target ，则nums[left] 一定是 target 。所以我们只需要判断 left 没越界并且nums[left]==target ，我们就找到了左端，否则就是不存在 target 。**

查找右侧端点:**
就是当nums[mid] == target时让 left=mid+1 ，分析方法和查找左侧端点完全一样，这里不再赘述。

代码1

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:   
        n = len(nums)
        if n == 0 or nums[n-1] < target or nums[0] > target:  # 特判，直接返回
            return [-1, -1]
        # 第一个while，找左端点
        left, right = 0, n-1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                right = mid - 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        if left < n and nums[left] == target:
            a = left
        else:  # 不存在target,就可以直接返回了
            return [-1, -1]
        # 第二个while，找右端点
        left, right = 0, n-1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        if right >= 0 and nums[right] == target:
            b = right
        return [a, b]

代码2

两个while循环只有等号时不一样，所以可以用一个变量将两个循环合并

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:   
        def binary_search(left, right, isLeft):
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    if isLeft:    right = mid - 1
                    else:    left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
                else:
                    left = mid + 1
            if isLeft: 
                return left if (left<n and nums[left] == target) else -1
            else:
                return right if (right >= 0 and nums[right] == target) else -1
        n = len(nums)
        if n == 0 or nums[n-1] < target or nums[0] > target:  # 特判，直接返回
            return [-1, -1]
        a = binary_search(0, n-1, True)
        b = binary_search(0, n-1, False)
        return [a, b]

时空复杂度

同方法1