[数据结构与算法]leetcode 34. 在排序数组中查找元素的第一个和最后一个位置

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

时间复杂度要求：$O(\log n)$

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

示例 4：

输入：nums =[5,7,7,8,8,10], target = 4或11
输出：[-1,-1]

简单分析下：本题数组有序但元素未必唯一了，因此可能找到多个target，我们需要做的就是确定这些连续target的左边界和右边界位置。依然是通过二分查找来搜索，只不过标准二分是mid找到一个target就直接return，此时while循环没有退出。而这里找边界，则不能找到一个target就return，必须通过left，right汇聚然后while循环退出，相应的left/right就对应左/右边界。左右边界的查找还是自己举例最为清晰。

解法一

1、二分查找target左右边界

二分查找左边界：找不到返回-1

1. nums[mid] == target则right = mid - 1继续往左逼近，其他与二分查找没有区别
2. 举例可知，能找到target的情况下，跳出循环时nums[left]=target 是其左边界，返回left即可
   • 换个角度理解为什么left是最终的左边界而不是right：在能找到target也就是存在nums[mid]=target的情况时，right = mid-1，那么while退出时必然right不可能是target了【直接举个例子更清晰】
3. 找不到target的情况下，跳出循环时nums[left] != target，令left = -1返回

二分查找右边界：找不到返回-1

1. nums[mid] == target则left = mid + 1继续往左逼近，其他不变

2. 举例可知，能找到target的情况下，跳出循环时nums[right]=target是其右边界，返回right即可

3. 找不到target的情况下，nums[right] != target，令right = -1返回

nums空时的越界问题

注意：nums为空集时，初始left = 0, right = 1，本来标准二分不会越界的，但是这里找边界添加了if nums[right/left]==target判断，那就会left/right = 0/-1，会越界，需单独处理

2、返回情况

1. target能被找到：左边界/右边界最终下标，return [left_border, right_border]
2. target找不到，return [-1, -1]
   • 2.1 target在数组范围内：左边界/右边界最终下标对应不到target，此时都被赋值为-1了！！
   • 2.2 target不在数组范围内：判断下数组max和min即可
   • 2.3 数组是空集

3、python实现1【推荐】

时间复杂度：$2?O(\log N)$，调用两次二分查找

执行用时：36 ms, 在所有 Python3 提交中击败了75.41% 的用户
内存消耗：15.9 MB, 在所有 Python3 提交中击败了86.09% 的用户

参考题解

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
		# 返回情况2.2 2.3
        if not nums or nums[0] > target or nums[-1] < target:
            return [-1, -1]
        else:    # 返回情况 1， 2.1    
            left_border = self.binary_search_left_border(nums, target, 0, len(nums)-1)
            right_border = self. binary_search_right_border(nums, target, 0, len(nums)-1)
            return [left_border, right_border]
        

    def binary_search_left_border(self, nums, target, left, right) -> int:
        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 nums[left] == target:
            return left
        else:
            return -1

    def binary_search_right_border(self, nums, target, left, right) -> int:
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                left = mid + 1 # 向右逼近
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        if nums[right] == target:
            return right
        else:
            return -1

4、python实现2

这里的分类和二分搜索与上面有些不同，个人觉得没有上面写的清楚，可以做个参考。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # border都差了一位
        left_border = self.binary_search_border_left(nums, 0, len(nums)-1, target) 
        right_border = self.binary_search_border_right(nums, 0, len(nums)-1, target) 
        # target在数组范围之外,注意是or！！
        if left_border == -2 or right_border == -2:
            return [-1, -1]
        # 能找到target（一个或连续多个）需满足 (left - right) >= 0
        elif ((right_border-1)-(left_border+1)) >= 0:
            return [left_border+1, right_border-1]
        else: # target 在数组范围之内，但是不在数组内
            return [-1, -1]
        

    def binary_search_border_left(self, nums, low, high, target):
        left_border = -2
        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] >= target:
                high = mid -1
                left_border = high
            else:
                low = mid + 1
        return left_border


    def binary_search_border_right(self, nums, low, high, target):
        right_border = -2
        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] <= target:
                low = mid + 1
                right_border = low
            else:
                high = mid - 1
        return right_border