在排序数组中查找元素的第一个和最后一个位置（二分、lower_bound、upper_bound）

Leetcode 每日一题
题目链接： 34. 在排序数组中查找元素的第一个和最后一个位置
难度： 中等
解题思路： 这道题题意很明显，就是二分查找。即为C++中的 lower_bound 和 upper_bound 函数。这里给出python3的版本。
题解：

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if len(nums) == 0:
            return (-1, -1)
        # 向左二分
        def lower_bound(nums, target):
            l, r = 0, len(nums) - 1
            res = -1
            if l == r and target == nums[l]:
                return 0
            while l < r:
                mid = (l + r) // 2 # 向下取整

                if target <= nums[mid]:
                    r = mid
                    res = mid
                else:
                    l = mid + 1

            if res == -1 and target == nums[r]: # 右边界
                res = r

            if res != -1 and target != nums[res]: # 未找到
                    res = -1
            
            return res

        # 向右二分
        def upper_bound(nums, target):
            l, r = 0, len(nums) - 1
            res = -1
            if l == r and target == nums[l]:
                return 0
            while l < r:
                mid = (l + r) // 2 + 1 # 向上取整

                if target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid
                    res = mid

            if res == -1 and target == nums[r]: # 左边界
                res = r

            if res != -1 and target != nums[res]: # 未找到
                    res = -1
            return res

        return (lower_bound(nums, target),upper_bound(nums, target))

本文地址：https://blog.csdn.net/qq_37753409/article/details/110422750