如何高效找出排序数组中被移动元素的索引？

针对原有序数组移动单个元素后的查找需求，无需使用逐个比对的低效方法，可利用二分查找快速定位异常点，将时间复杂度从O(n)降至O(logn)。

核心思路 #

原数组为严格递增序列，移动单个元素后，新数组中只会存在一处破坏递增规律的位置：

• 若元素从后往前移（如示例中的6移到4前面），会出现modified[i] > modified[i+1]的情况，此时modified[i]即为被移动元素；
• 若元素从前往后移（如1移到数组末尾），会出现modified[i-1] > modified[i]的情况，此时modified[i]即为被移动元素。

实现代码（Python） #

import bisect

def find_moved_element(original, modified):
    n = len(modified)
    left, right = 0, n - 1
    moved_idx = -1

    # 二分查找定位异常点
    while left < right:
        mid = (left + right) // 2
        # 找到破坏递增的位置
        if modified[mid] > modified[mid + 1]:
            # 结合原数组判断被移动元素：原数组中它的索引应更大
            orig_idx_mid = bisect.bisect_left(original, modified[mid])
            orig_idx_next = bisect.bisect_left(original, modified[mid + 1])
            moved_idx = mid if orig_idx_mid > orig_idx_next else mid + 1
            break
        # 当前元素与原数组一致，异常点在右侧
        elif modified[mid] == original[mid]:
            left = mid + 1
        # 当前元素比原数组对应位置小，异常点在左侧
        else:
            right = mid

    # 处理元素移到数组开头/结尾的边界情况
    if moved_idx == -1:
        moved_idx = 0 if modified[0] != original[0] else n - 1

    return modified[moved_idx], moved_idx

代码说明 #

1. 用bisect_left在原有序数组中快速查找元素索引，避免list.index()的O(n)耗时；
2. 二分查找仅需log₂n次比对即可定位异常点，大幅提升大数组场景下的效率；
3. 覆盖了元素移到开头、结尾等所有边界场景。

示例验证 #

• 原数组：[1,2,3,4,5,6]，修改后数组：[1,2,3,6,4,5]
• 调用函数返回：(6, 3)，符合预期。

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