JavaScript 算法：是否有更好的方法从排序数组中获取异常值，其中任意两个连续数组之间的差值为 1

Question

我有一个排序数组，其中除一个数字外，任意两个连续的数组之间的差为 1，并且该函数将 return 数字的索引。比如[100, 101, 102, 107]，就要return3。这是我的尝试。

const sortedArray =  [100, 101, 102, 107]

function getAnomaly(sortedArray) {
    const index = sortedArray.findIndex((val, index, self) => {
        return val + 1 !== (self[index + 1] ?? val + 1)
    })
    
    return index === -1 ? -1 : index + 1
}

getAnomaly(sortedArray)

需要 O(n) 扫描数组并找到数字。考虑到数组已排序，我想知道是否有更有效的方法来做到这一点？但我不确定具体如何。

Answer 1

是的，你可以提高效率，因为给函数 getAnomaly 的数组已经排序，答案与你已经添加的标签相同，即 二分搜索.

对于你在数组中得到的每个中间值，如果它等于它是index + the lowest value，你可以安全地得出结论，它之前的所有元素都是正确排列的，连续差为1，左半部分可以是忽略。

如果排列正确，答案在数组的右边。如果没有，记录索引，向左移动

注意对齐中断的那一刻，您不能快速return 索引，因为 sortedArray[ mid ] 可以与其邻居正确排列，而它左边的一些数字可能是造成差距的罪魁祸首。

片段：

const sortedArray =  [100, 101, 102, 107];

function getAnomaly(sortedArray) {
    let low = 0, high = sortedArray.length - 1;
    let ans = -1;
    while(low <= high){
      let mid = low + ((high - low) >> 1);
      if(sortedArray[ mid ] === sortedArray[0] + mid){
        low = mid + 1;
      }else{
        ans = mid;
        high = mid - 1;
      }
    }
    return ans;
}

console.log(getAnomaly(sortedArray));

时间复杂度： O(log(n)) 因为我们每次都将数组中的搜索 space 分成两半。

Space 复杂度： O(1)

JavaScript 算法：是否有更好的方法从排序数组中获取异常值，其中任意两个连续数组之间的差值为 1

JavaScript Algorithm: Is there a better way to get the anomaly from a sorted array where the difference between any two consecutive is 1

javascript

algorithm

binary-search