python 在排序数组中查找元素的第一个和最后一个位置多种解法

编程小白狼

发布于 2024-12-31 08:19:05

1.4K0

二分查找：基于二分查找的算法可以在 O(log n) 的时间复杂度内解决该问题。具体实现方式是，先使用二分查找找到该元素的位置，然后向左和向右扩展，直到找到第一个和最后一个位置。代码如下：

def searchRange(nums, target):
    def binarySearch(nums, target, lower):
        left, right = 0, len(nums) - 1
        ans = len(nums)
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] > target or (lower and nums[mid] >= target):
                right = mid - 1
                ans = mid
            else:
                left = mid + 1
        return ans

    leftIdx = binarySearch(nums, target, True)
    rightIdx = binarySearch(nums, target, False) - 1

    if leftIdx <= rightIdx and rightIdx < len(nums) and nums[leftIdx] == target and nums[rightIdx] == target:
        return [leftIdx, rightIdx]

    return [-1, -1]

线性扫描：线性扫描的思路是从左到右遍历数组，记录第一次出现目标值的位置，然后继续遍历数组，直到找到最后一次出现目标值的位置，代码如下：

def searchRange(nums, target):
    first, last = -1, -1
    for i in range(len(nums)):
        if nums[i] == target:
            if first == -1:
                first = i
            last = i
    return [first, last]

使用 Python 内置函数：Python 中有内置函数 bisect_left 和 bisect_right 可以帮助我们实现二分查找。代码如下：

import bisect

def searchRange(nums, target):
    left = bisect.bisect_left(nums, target)
    right = bisect.bisect_right(nums, target) - 1
    if left <= right and nums[left] == target and nums[right] == target:
        return [left, right]
    return [-1, -1]

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-01-17，如有侵权请联系 cloudcommunity@tencent.com 删除

排序