查找超大有序数组中目标元素的最后出现位置

本文介绍如何在未知长度的超大有序数组中高效定位某元素最后一次出现的索引，结合指数搜索确定边界与改进版二分查找精确定位，时间复杂度为 o(log k)，其中 k 是目标元素最后出现位置的索引。

在处理“无限大”或规模极大且长度未知的有序数组时，传统二分查找因依赖已知数组长度而失效。此时需采用两阶段策略：首先通过指数搜索（Exponential Search） 快速定位包含目标元素的合理右边界；随后在该区间内执行右倾二分查找（Rightmost Binary Search），精准定位最后一个匹配位置。

第一阶段：指数扩展确定搜索范围

由于数组长度未知，我们从区间 [0, 1] 开始，不断将右边界 end 翻倍（即 end = end * 2），直到 arr[end] >= target 或发生越界。注意关键修正：判断条件应为 arr[end]

越界处理使用 try-except 捕获 IndexError，一旦越界即终止扩展，并返回 -1（表示目标不存在于已探查范围内）。

第二阶段：右倾二分查找定位最后出现位置

标准二分查找找到任意一个匹配即可，但本题要求最后一个下标。因此，在 arr[mid] == target 时，不能立即返回，而需验证是否为右边界：

• 若 mid 是数组末尾（mid == len(arr) – 1），或 arr[mid + 1] != target，则 mid 即为答案；
• 否则，说明右侧仍有相同元素，应向右半区递归搜索：binarySearch(target, arr, mid + 1, end)。

⚠️ 注意：原始代码中 elif arr[mid+1] != target 存在越界风险（当 mid 为最后一索引时访问 mid+1）。改进版应先检查 mid == len(arr)-1，再判断 arr[mid+1]，或统一用 mid == len(arr)-1 or arr[mid+1] != target（Python 中 or 短路求值可避免越界）。

以下是完整、健壮的实现：

def binary_search_last(target, arr, start, end):     if start > end:         return -1     mid = (start + end) // 2     if arr[mid] == target:         # 检查是否为最后一个出现位置         if mid == len(arr) - 1 or arr[mid + 1] != target:             return mid         else:             return binary_search_last(target, arr, mid + 1, end)     elif arr[mid] > target:         return binary_search_last(target, arr, start, mid - 1)     else:  # arr[mid] < target         return binary_search_last(target, arr, mid + 1, end)  def exponential_search_last(target, arr):     if not arr:         return -1     if arr[0] == target:         # 向右线性扫描找最后一个？不——仍用二分更优；但需先确认右边界         pass      # 阶段1：指数扩展找上界     start, end = 0, 1     while end < len(arr) and arr[end] < target:         start = end         end *= 2      # 若 end 超出数组长度，收缩至末尾     if end >= len(arr):         end = len(arr) - 1      # 若当前 arr[end] < target，说明 target 不存在     if end >= len(arr) or arr[end] < target:         return -1      # 阶段2：在 [start, end] 内查找最后出现位置     return binary_search_last(target, arr, start, end)  # 主程序 if __name__ == "__main__":     arr = list(map(int, input().split()))     target = int(input())     result = exponential_search_last(target, arr)     print(result)

✅ 示例验证：
输入：1 2 7 7 14 19 23 和 7 → 输出 3（0-indexed，即第 4 个元素，第二个 7 的位置）
输入：5 5 5 5 和 5 → 输出 3

? 关键总结：

• 指数搜索将初始范围探测复杂度降至 O(log k)，避免遍历整个巨型数组；
• 右倾二分必须严格处理边界条件，优先检查 mid + 1 是否越界；
• 整体算法时间复杂度为 O(log k)，空间复杂度 O(log k)（递归栈深度）；
• 适用于日志文件、数据库索引、流式排序数据等真实场景中“巨大且动态长度”的有序序列查询。