# Search an element in sorted rotated array

5.23K views
0

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

0

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