查找升序整数数组中目标值的首尾索引问题求助

嘿，我一眼就发现你代码里的问题啦！

问题根源 #

你第一个for循环里的else块是和if语句绑定的，而不是和for循环绑定的。这就导致了一个致命逻辑错误：只要第一个元素不等于目标值，程序就会直接返回[-1,-1]，根本不会继续检查列表后面的元素。

拿你的测试用例来说，列表第一个元素是3，不等于目标值5，代码立刻触发return [-1,-1]，直接终止了程序，自然找不到后面存在的5了。

修复后的代码 #

我们需要调整逻辑：只有当整个第一个循环结束后，确认完全找不到目标值时，才返回[-1,-1]。下面是修正后的代码：

nums = [3,4,5,5,5,6,7,8,9]
target = 5
class Solution:
    def searchRange(self,nums, target):
        left_index = -1
        # 遍历寻找左边界
        for i in range(len(nums)):
            if nums[i] == target:
                left_index = i
                break
        # 如果左边界未找到，直接返回[-1,-1]
        if left_index == -1:
            return [-1,-1]
        # 反向遍历寻找右边界
        right_index = -1
        for j in range(len(nums)-1,-1,-1):
            if nums[j] == target:
                right_index = j
                break
        return [left_index, right_index]
x = Solution()
print(x.searchRange(nums,5))

运行这段代码，就能得到你期望的输出[2,4]啦。

进阶优化：二分查找 #

因为你的列表是升序排列的，用线性遍历虽然简单，但在列表元素很多时效率较低。更高效的方式是用二分查找来定位左右边界，时间复杂度可以降到O(log n)：

class Solution:
    def searchRange(self, nums, target):
        # 寻找左边界的辅助函数
        def find_left():
            left, right = 0, len(nums)-1
            res = -1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] == target:
                    res = mid
                    right = mid - 1  # 找到匹配后继续往左探索更早的位置
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return res
        
        # 寻找右边界的辅助函数
        def find_right():
            left, right = 0, len(nums)-1
            res = -1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] == target:
                    res = mid
                    left = mid + 1  # 找到匹配后继续往右探索更晚的位置
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return res
        
        left_pos = find_left()
        # 左边界不存在的话，直接返回[-1,-1]
        if left_pos == -1:
            return [-1,-1]
        right_pos = find_right()
        return [left_pos, right_pos]

内容的提问来源于stack exchange，提问作者user14901649