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