Search an element in sorted rotated array
Suppose an array sorted in ascending order 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]
).
You are given a target value to search. If found in the array return its index, otherwise return -1
.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1
Even though the array is rotated, we can still use binary search here by finding the point of rotation using the function findPivotIndex() as shown below. Once we find the pivot (point of rotation), divide the array in 2 halves, each of which will still be in sorted order and apply binary search on each one of those halves and collate the results and return the index.
Javascript code below:-
/** * @param {number[]} nums * @param {number} target * @return {number} */ var search = function(nums, target) { var pivot = findPivotIndex(nums); var firstHalf = nums.slice(0, pivot); var index = binSearch(firstHalf, target); if (index === -1) { var index2 = binSearch(nums.slice(pivot), target); index = (index2 === -1) ? -1 : firstHalf.length + index2; } return index; }; // binary search var binSearch = function (arr, x) { var start=0, end=arr.length-1; // Iterate while start not meets end while (start<=end){ // Find the mid index var mid=Math.floor((start + end)/2); // If element is present at mid, return True if (arr[mid]===x) return mid; // Else look in left or right half accordingly else if (arr[mid] < x) start = mid + 1; else end = mid - 1; } return -1; } // find the point of rotation in array var findPivotIndex = function(nums) { var start = 0, end = nums.length - 1, mid; mid = start + parseInt((end - start) / 2); var last = nums[nums.length - 1]; while (start <= end) { if (nums[mid] > last) { start = mid + 1; } else if (nums[mid] < last) { end = mid - 1; } else break; mid = start + parseInt((end - start) / 2); } return mid; }