JavaScript Algorithm: Is there a better way to get the anomaly from a sorted array where the differe-CodePudding

I have a sorted array where the difference between any two consecutive is 1 except for one number, and the function is going to return the index of the number. For example, [100, 101, 102, 107], it is going to return 3. Here is my attempt.

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)

It takes O(n) to scan the array and find the number. I wonder if there is a more efficient way to do it given the array is sorted? But I am not sure exactly how.

CodePudding user response：

Yes you can make it more efficient since the array given to function getAnomaly is already sorted and the answer is the same as you have already added the tag, that is binary search.

For every mid value you get in the array, if it equals it's index the lowest value, you can safely conclude that all the elements before it are arranged correctly with a consecutive difference of 1 and the left half can be ignored.

If it is arranged correctly, answer lies in the right side of the array. If not, record the index and move towards the left.

Note that the moment the alignment breaks, you can't quickly return the index since the sortedArray[ mid ] can be arranged correctly with it's neighbours and some number to it's left can be the culprit for the gap.

Snippet:

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));

Time Complexity: O(log(n)) since we divide the search space in the array each time by half.

Space Complexity: O(1)