Searching an Element in a Rotated Sorted Array - JavaScript

Question

Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). How do you find an element in the rotated array efficiently? You may assume no duplicate exists in the array.

Origin from: LeetCode


Solution

// Time complexity: O(log n)
function rotatedBinarySearch(arr, k) {
    var l = 0,
        r = arr.length - 1;
    while (l <= r) {
        var m = Math.floor((l + r) / 2);

        if (arr[m] == k) {
            return m;
        }

        if (arr[l] < arr[m]) {
            if (arr[l] <= k && k < arr[m]) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        } else {
            if (arr[m] <= k && k < arr[r]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
    }
    return -1;
}

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

Demo

Yang Zhao

Read more posts by this author.


Comment