本文介绍如何在未知长度的超大有序数组中高效定位某元素最后一次出现的索引，结合指数搜索确定边界与改进版二分查找精确定位，时间复杂度稳定为 o(log k)，其中 k 为目标元素最后出现位置的索引。
在处理“无限大”或规模极大且长度未知的有序数组时，传统二分查找无法直接应用——因为无法获知右边界 end。此时需采用两阶段策略：第一阶段用指数搜索（Exponential Search） 快速定位一个包含目标元素的合理右边界区间；第二阶段在该区间内执行定制化二分查找，专门寻找目标值的最后一次出现位置（即最右侧满足 arr[i] == target 的索引）。
✅ 核心思路解析
- 指数搜索定界：从区间 [0, 1] 开始，不断将右端点翻倍（end = end * 2），直到 arr[end] >= target 或发生越界。注意：此处判断条件必须为
-
改进二分查找求末位：标准二分查找到目标后即返回，但本题需继续向右探索。因此，当 arr[mid] == target 时，应检查 mid+1 是否仍为 target：
- 若 mid 是数组末尾，或 arr[mid + 1] != target，则 mid 即为答案；
- 否则，目标的最后位置必然在 [mid + 1, end] 区间内，递归/迭代向右搜索。
? 完整可运行代码（Python）
def binary_search_last(target, arr, start, end):
if start > end:
return -1
mid = (start + end) // 2
try:
mid_val = arr[mid]
except IndexError:
return -1
if mid_val == target:
# 检查是否为最后一个 occurrence：是末尾 或 下一个不等于 target
if mid == len(arr) - 1 or arr[mid + 1] != target:
return mid
else:
# 继续向右搜索更靠后的 occurrence
return binary_search_last(target, arr, mid + 1, end)
elif mid_val < target:
return binary_search_last(target, arr, mid + 1, end)
else: # mid_val > target
return binary_search_last(target, arr, start, mid - 1)
def exponential_search_last(target, arr):
if not arr:
return -1
# Step 1: Find upper bound via exponential growth
end = 1
while end < len(arr) and arr[end] < target:
end *= 2
# Now search in [end//2, min(end, len(arr)-1)]
start = end // 2
end = min(end, len(arr) - 1)
# Step 2: Binary search for last occurrence in bounded range
return binary_search_last(target, arr, start, end)
# 主程序入口
if __name__ == "__main__":
try:
arr = list(map(int, input().split()))
target = int(input())
result = exponential_search_last(target, arr)
print(result)
except (ValueError, IndexError):
print(-1)⚠️ 关键注意事项
- 越界防护必须显式处理：arr[mid + 1] 和 arr[end] 访问前需用 try-except 或边界判断（如 mid
- 指数搜索终止条件要严谨：原错误代码中 while arr[end]
- 初始区间选择：从 [0, 1] 启动合理，但若数组极小（如仅 1 个元素），end = 1 可能越界，因此 end = min(end, len(arr)-1) 是安全兜底。
- 时间复杂度：指数阶段最多执行 O(log k) 步（k 为答案索引），二分阶段同样 O(log k)，总复杂度为 O(log k)，优于线性扫描的 O(n)。
✅ 示例验证
输入：
1 2 7 7 14 19 23 7
输出：3（索引从 0 开始，arr[3] == 7 且 arr[4] == 14 ≠ 7，符合要求）
该方案鲁棒性强，适用于真实场景中日志索引、分布式排序数据分片等“理论上无限、实践中极大”的有序数据结构查询需求。
