欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-22 16:35:57
Leetcode 每日一题题目链接: 34. 在排序数组中查找元素的第一个和最后一个位置难度: 中等解题思路: 这道题题意很明显,就是二分查找。即为C++中的 lower_bound 和 upper_bound 函数。这里给出python3的版本。题解:class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: if len(nums) == 0:...

Leetcode 每日一题
题目链接: 34. 在排序数组中查找元素的第一个和最后一个位置
难度: 中等
解题思路: 这道题题意很明显,就是二分查找。即为C++中的 lower_boundupper_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

相关标签: Leetcode