请输入图片描述

一个非递减的整数数组，查找target数字起始和结束的索引，如果没有找到target数字输出-1,-1,确保时间复杂度是logn

代码

def search_range(nums, target):
    def find_first(nums, target):
        start, end = 0, len(nums) - 1
        result = -1
        while start <= end:
            mid = (start + end) // 2
            if nums[mid] == target:
                result = mid
                end = mid - 1  # 继续在左侧搜索
            elif nums[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
        return result

    def find_last(nums, target):
        start, end = 0, len(nums) - 1
        result = -1
        while start <= end:
            mid = (start + end) // 2
            if nums[mid] == target:
                result = mid
                start = mid + 1  # 继续在右侧搜索
            elif nums[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
        return result

    first_occurrence = find_first(nums, target)
    last_occurrence = find_last(nums, target)

    return [first_occurrence, last_occurrence]

# 示例
nums = [5, 7, 7, 8, 8, 10]
target = 8
result = search_range(nums, target)
print(result)  # 输出：[3, 4]

这道题目的时间复杂度？

这个算法分别查找目标数字的第一次出现和最后一次出现的位置，从而确定范围。时间复杂度是 O(logn)，因为在二分查找中，每一步都将搜索范围减半。如果目标数字不存在，返回 [-1, -1]。

对于该算法，时间复杂度是 O(logn)。这是因为在每个二分查找迭代中，搜索范围都被减半。具体来说：

找第一次出现的位置：

如果中间元素小于目标值，说明目标值可能在右侧，因此将搜索范围缩小到右半部分。
如果中间元素等于目标值，说明目标值可能在左侧，继续在左侧搜索。
如果中间元素大于目标值，说明目标值可能在左侧，继续在左侧搜索。
每次都将搜索范围缩小一半，因此时间复杂度是 O(logn)。
找最后一次出现的位置：

如果中间元素小于目标值，说明目标值可能在右侧，因此将搜索范围缩小到右半部分。
如果中间元素等于目标值，说明目标值可能在右侧，继续在右侧搜索。
如果中间元素大于目标值，说明目标值可能在左侧，继续在左侧搜索。
每次都将搜索范围缩小一半，因此时间复杂度是 O(logn)。
因此，整体算法的时间复杂度是 O(logn)。

如何数学推导这道题目的时间复杂度？

对于这道题目，可以通过数学推导来分析时间复杂度。首先，我们要理解算法的关键部分是二分查找。

二分查找时间复杂度分析：
在二分查找中，每一轮迭代都将搜索范围减半。设初始数组长度为 n，那么经过 k 轮迭代后，数组长度将缩小为 n / 2^k。当数组长度缩小到 1 时，即 n / 2^k = 1，解得 k = log₂n。

因此，二分查找的时间复杂度是 O(logn)。

针对本题的时间复杂度分析：
找第一次出现的位置：

进行一次二分查找，时间复杂度是 O(logn)。
找最后一次出现的位置：

进行一次二分查找，时间复杂度是 O(logn)。
整体算法是进行两次二分查找，因此总的时间复杂度是 O(logn)。

这样的推导基于二分查找的核心思想，即每一步都将搜索范围减半。这种推导方法是一种常见的对二分查找时间复杂度进行分析的方式。

标签: none