Search Rotated Sorted Array Editorial

Practice Problem Link: Search Rotated Sorted Array | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Practice Problem

You are given a list of unique integers which are sorted but rotated at some pivot. You are also given a target value and you have to find its index in the list. If it is not present in the list, return -1.

Naive Approach

A simple solution is to just iterate the array and find the index of the target value by comparing each element of the array with the target value.

Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Implementation

C++

int getElementIndex(vector<int> array, int target) {
   int indx = -1;
   for (int i = 0; i < array.size(); i++) {
       if (array[i] == target) {
           indx = i;
       }
   }
   return indx;
}

Java

class Solution {
   int getElementIndex(int[] array, int target) {
       int indx = -1;
       for (int i = 0; i < array.length; i++) {
           if (array[i] == target) {
               indx = i;
           }
       }
       return indx;
   }
}

Optimal Solution

The array can be treated as two different sorted arrays. All we need to do is to find the point from where the array needs to be broken down into two different arrays.

• To find that point we can perform a binary search to find the only element which is greater than its next element.
• After finding that point we can apply binary search in both parts of the array to find the index of the key.

Analysis

• Time Complexity: O(log(n))
• Space Complexity: O(1)

Implementation

C++

int findRotatedIndx (vector<int> arr, int low, int high) {
   if (high >= low) {
       int mid = (high + low) / 2;
       if (mid != 0 && arr[mid - 1] > arr[mid]) {
           return mid - 1;
       } else if (arr[0] >= arr[mid]) {
           return findRotatedIndx (arr, low, mid - 1);
       } else {
           return findRotatedIndx (arr, mid + 1, high);
       }
   }
   return - 1;
}
int binarySearch (vector<int> arr, int low, int high, int target) {
   if(high >= low) {
       int mid = (high + low) / 2;
       if (arr[mid] == target) {
           return mid;
       } else if(arr[mid] > target) {
           return binarySearch (arr, low, mid - 1, target);
       } else {
           return binarySearch (arr, mid + 1, high, target);
       }
   }
   return - 1;
}
int getElementIndex(vector<int> array, int target) {
   int n = array.size();
   int rotatedIndx = findRotatedIndx (array, 0, n - 1);
   if (rotatedIndx == -1) {
       return binarySearch (array, 0, n - 1, target);
   }
   if (array[0] <= target) {
       return binarySearch (array, 0, rotatedIndx, target);
   } else {
       return binarySearch (array, rotatedIndx + 1, n - 1, target);
   }
}

Java

class Solution {
   int findRotatedIndx (int[] arr, int low, int high) {
       if (high >= low) {
           int mid = (high + low) / 2;
           if (mid != 0 && arr[mid - 1] > arr[mid]) {
               return mid - 1;
           } else if (arr[0] >= arr[mid]) {
               return findRotatedIndx (arr, low, mid - 1);
           } else {
               return findRotatedIndx (arr, mid + 1, high);
           }
       }
       return -1;
   }
   int binarySearch (int[] arr, int low, int high, int target) {
       if(high >= low) {
           int mid = (high + low) / 2;
           if (arr[mid] == target) {
               return mid;
           } else if(arr[mid] > target) {
               return binarySearch (arr, low, mid - 1, target);
           } else {
               return binarySearch (arr, mid + 1, high, target);
           }
       }
       return - 1;
   }
   int getElementIndex(int[] array, int target) {
       int n = array.length;
       int rotatedIndx = findRotatedIndx (array, 0, n - 1);
       if (rotatedIndx == -1) {
           return binarySearch (array, 0, n - 1, target);
       }
       if (array[0] <= target) {
           return binarySearch (array, 0, rotatedIndx, target);
       } else {
           return binarySearch (array, rotatedIndx + 1, n - 1, target);
       }
   }
}