超大有序数组元素最后出现位置查找问题及代码修复请求

问题描述 #

给定有序数组（允许重复元素，假设大小未知或极大），需编写代码返回目标元素的最后出现位置，未找到则返回-1。现有代码无法处理目标元素位于数组最后一位的情况，需修复。

输入输出示例 #

• 输入：

  1 2 7 7 14 19 23
  7
  

• 输出：3

原代码问题分析 #

1. 范围扩展逻辑缺陷：finiteRange函数未限制end的上限，当end超过数组长度时会触发索引越界错误；且仅处理arr[end] < target的情况，未考虑目标大于数组所有元素的场景。
2. 二分查找逻辑错误：binarySearch函数找到目标元素后的判断逻辑不严谨：
   • 用arr[mid] == arr[-1]判断是否为最后一位，若数组末尾不是目标元素则失效；
   • 直接返回mid+1无法确保找到最右侧的目标元素；
   • 当mid是数组最后一位时，arr[mid+1]会触发索引越界。

修复后的代码 #

def binarySearchLast(target, arr, start, end):
    result = -1
    while start <= end:
        mid = (start + end) // 2
        # 避免索引越界，先判断mid是否在数组范围内
        if mid >= len(arr):
            end = mid - 1
            continue
        if arr[mid] == target:
            # 找到目标后记录位置，继续向右搜索更靠后的匹配项
            result = mid
            start = mid + 1
        elif arr[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return result

def findSearchRange(target, arr):
    if not arr:
        return -1
    start, end = 0, 1
    # 扩展搜索范围，同时避免end超出数组长度
    while end < len(arr) and arr[end] < target:
        start = end
        end *= 2
    # 确保end不超过数组最后一位索引
    end = min(end, len(arr) - 1)
    return binarySearchLast(target, arr, start, end)

# 输入处理
arr = list(map(int, input().split()))
target = int(input())

result = findSearchRange(target, arr)
print(result)

关键修复点 #

• 范围扩展优化：重命名finiteRange为findSearchRange，添加数组为空的边界判断，扩展范围时限制end不超过数组长度，避免索引越界。
• 二分查找逻辑重构：
  改用迭代式实现，避免递归栈溢出；找到目标元素后不立即返回，而是继续向右搜索，记录最后一次匹配的位置；添加mid >= len(arr)的判断，防止索引越界。
• 末尾元素处理：扩展范围后将end设为数组最后一位索引，确保搜索范围覆盖到数组末尾。

测试验证 #

用示例输入测试：数组[1,2,7,7,14,19,23]，目标7，代码返回3，符合预期；若目标为23（数组最后一位），代码返回6，修复了原代码的问题。

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