Search an element in sorted rotated array

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

Answered question
Write your answer.

Categories