JavaScript算法：有序差1数组查找异常值索引的更优方案咨询

优化方案：使用二分查找实现*O(logn)*时间复杂度 #

因为数组仅存在一处异常，其余相邻元素差值均为1，存在核心规律：无异常的区间内，任意下标i位置的元素值必然等于arr[0] + i。异常点左侧所有元素都符合该规律，异常点及右侧所有元素都会比该公式计算的预期值大，因此可以用二分查找快速定位异常点，不需要遍历全数组。

实现代码 #

function getAnomaly(sortedArray) {
    const len = sortedArray.length
    // 数组长度小于2不存在相邻元素，无异常
    if (len < 2) return -1
    let left = 0
    let right = len - 1
    let anomalyIndex = -1
    while (left <= right) {
        const mid = Math.floor((left + right) / 2)
        // 计算mid位置的预期值
        const expected = sortedArray[0] + mid
        if (sortedArray[mid] === expected) {
            // 左半段无异常，去右半段查找
            left = mid + 1
        } else {
            // 记录当前可能的异常点，去左半段找更靠前的异常点
            anomalyIndex = mid
            right = mid - 1
        }
    }
    return anomalyIndex
}

// 测试用例
const sortedArray = [100, 101, 102, 107]
console.log(getAnomaly(sortedArray)) // 输出3
console.log(getAnomaly([1,2,3,4])) // 输出-1

效率对比 #

• 原遍历方案时间复杂度为O(n)，空间复杂度O(1)
• 二分方案时间复杂度为O(logn)，空间复杂度O(1)，在数组长度较大时效率提升极为明显，比如长度为10万的数组仅需要最多17次查找即可得到结果。

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