Find Sorted Array Rotation - JavaScript

Question

Implement the following function, FindSortedArrayRotation, which takes as its input an array of unique integers that has been sorted in ascending order, then rotated by an unknown amount X where 0 <= X <= (arrayLength - 1). An array rotation by amount X moves every element array[i] to array[(i + X) % arrayLength]. FindSortedArrayRotation discovers and returns X by examining the array.

Origin from: LeetCode


Solution

// Time complexity: O(log n)
function findSortedArrayRotation(arr) {
    var l = 0,
        r = arr.length - 1;
    while (arr[l] > arr[r]) {
        var m = Math.floor((l + r) / 2);
        if (arr[r] < arr[m]) {
            l = m + 1;
        } else {
            r = m;
        }
    }
    return l;
}

var arr = [4, 5, 6, 7, 0, 1, 2];
findSortedArrayRotation(arr);

Demo

Yang Zhao

Read more posts by this author.


Comment