Learn how to search an element in a sorted rotated array.
Example
Input; [3, 4, 5, 1, 2] k = 1 Output: 3
The best way to search anything in a sorted array is by using binary search, we are also going to see two different solutions using it.
By splitting the sorted rotated array in two sub-arrays.
Conceptually this is how this approach works.
- Splitting the original array in two sub-arrays, so that we have two sorted arrays.
- Now use binary search on both of these sub-arrays to find the element.
- To make it more optimized, we can just find a pivot rather than actually splitting the array and search based on that.
As binary search uses the index of the array to determine the direction of the search, we can search from 0 to pivot for first sub-array and pivot to end for second sub-array.
Finding the pivot
Our pivot is the index of the element whose next element is less than it, which makes sure’s that after this element the array is rotated [3, 4, 5, 1, 2].
const findPivot = (arr, low, high) => {
if(high < low){
return - 1;
}
if(high === low){
return low;
}
let mid = Math.floor((low + high) / 2);
if (mid < high && arr[mid] > arr[mid + 1]) {
return mid;
}
if (mid > low && arr[mid] < arr[mid - 1]) {
return (mid - 1);
}
if (arr[low] >= arr[mid]) {
return findPivot(arr, low, mid - 1);
}
return findPivot(arr, mid + 1, high);
}
Binary search
const binarySearch = (arr, low, high, key) => {
if(high < low){
return -1;
}
let mid = Math.floor((low + high) / 2);
if(key === arr[mid]){
return mid;
}
if(key > arr[mid]){
return binarySearch(arr, mid + 1, high, key);
}
return binarySearch(arr, low, mid - 1, key);
}
Main function
const solution = (arr, key, n = arr.length) => {
const pivot = findPivot(arr, 0, arr.length - 1);
// If we didn't find a pivot, then
// array is not rotated at all
if (pivot == -1) {
return binarySearch(arr, 0, n - 1, key);
}
// If we found a pivot, then first
// compare with pivot and then
// search in two subarrays around pivot
if (arr[pivot] == key) {
return pivot;
}
if (arr[0] <= key){
return binarySearch(arr, 0, pivot - 1, key);
}
return binarySearch(arr, pivot + 1, n - 1, key);
}
Input: console.log(solution([3, 4, 5, 1, 2], 1)); Output: 3
Time complexity: O(logn)(pivot) + O(logn)(binary search) = O(logn).
Space complexity: O(1).
Efficient approach to search an element in sorted rotated array
In this approach rather than passing call instances of binary search, we modify the original binary search using the following approach.
1) Find the mid = (l + h)/2
2) If key is present at mid, return mid.
3) Else If arr[l..mid] is sorted
a) If key to be searched lies in range from arr[l]
to arr[mid], recur for arr[l..mid].
b) Else recur for arr[mid+1..h]
4) Else (arr[mid+1..h] must be sorted)
a) If key to be searched lies in range from arr[mid+1]
to arr[h], recur for arr[mid+1..h].
b) Else recur for arr[l..mid]
const binarySearch = (arr, l, h, key) => {
if(l > h) {
return -1;
}
let mid = Math.floor((l + h) / 2);
if(arr[mid] === key){
return mid;
}
// If arr[l...mid] first subarray is sorted
if(arr[l] <= arr[mid]){
// As this subarray is sorted, we can quickly check if key lies in half or other half
if(key >= arr[l] && key <= arr[mid]){
return binarySearch(arr, l, mid-1, key);
}
/*If key not lies in first half subarray, Divide other half into two subarrays,
such that we can quickly check if key lies in other half */
return binarySearch(arr, mid+1, h, key);
}
/* If arr[l..mid] first subarray is not sorted,
then arr[mid... h] must be sorted subarry*/
if (key >= arr[mid] && key <= arr[h]) {
return binarySearch(arr, mid + 1, h, key);
}
return binarySearch(arr, l, mid - 1, key);
}
Input: const arr = [ 4, 5, 6, 7, 8, 9, 1, 2, 3 ]; console.log(binarySearch(arr, 0, arr.length - 1, 3)); Output: 8
Time complexity: O(logn).
Space complexity: O(1).