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

题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 $O(logn)$ 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

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

示例 2:

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

解题思路

该数组是排序好的，可以使用二分查找
循环可以继续的条件是 l < r，这样退出循环的时候 l == r 成立，返回l或者r，需要注意的是：当搜索范围缩小到一个点的时候，需要单独判断。

取“中点”的操作有 2 种

• mid = l + (r - l) // 2，特点：在只有两个数的时候，靠近左边。
• mid = l + (r - l + 1) // 2，特点：在只有两个数的时候，靠近右边。

代码

class Solution:
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        left = self.__find_lower_bound(nums, target) #第一个元素的位置
        if left == -1: # 判断数组是否为空
            return [-1, -1]

        right = self.__find_up_bound(nums, target)# 最后一个元素的位置
        return [left, right]

    def __find_lower_bound(self, nums, target):
        # 找到小于等于 target 的第 1 个元素的索引
        size = len(nums)
        if size == 0:
            return -1
        l = 0
        r = size - 1
        while l < r:
            mid = l + (r - l) // 2# 在只有两个数的时候，取靠近左边的为mid。
            if nums[mid] < target:
                l = mid + 1 # 左端点不断右移
            else:
                r = mid
        # 最后还要单独判断一下
        if nums[l] != target:
            return -1
        return l

    def __find_up_bound(self, nums, target):
        # 找到大于等于 target 的最后 1 个元素的索引
        size = len(nums)
        if size == 0:
            return -1
        l = 0
        r = size - 1
        while l < r:
            mid = l + (r - l + 1) // 2# 在只有两个数的时候，取靠近右边的为mid。
            if nums[mid] > target:
                r = mid - 1 # 右端点不断左移
            else:
                l = mid
        # 最后还要单独判断一下
        if nums[l] != target:
            return -1
        return l

如有错误，请批评指正！