Search a Rotated Array
Short Summary
We are given a sorted array which is rotated an arbitrary number of times. The task is to search for a given number in that array and if found return the index if not found return -1. Array contains unique numbers.
I/O Example
inputArr = [ 4, 5, 6, 1, 2, 3 ];
searchKey = 6;
inputArr2 = [ 4, 5, 6, 1, 2, 3 ];
searchKey2 = 3;
const output = myFunction(inputArr, searchKey);
const output2 = myFunction(inputArr2, searchKey2);
// output -> 2
// output2 -> 5Explanation and Walk-through
We want to search in a sorted array which has been rotated a number of times. Rotated means that the start index of the array does not hold the smallest item anymore, but an arbitrary index within the array does. Think of it as a sorted array broken down into two pieces and those pieces have switched positions.
Hence [1,2,3,4,5,6] becomes [4,5,6,1,2,3].
Let's identify the important size factors:
inputArray.length -> N
Size of the input array is important because in directly affects the number of comparisons we need to make before we can conclude.
Trying all possible combinations
With simple thinking we can compare our searchKey to all of the elements in inputArr, this would take N comparisons to complete. To perform these comparisons we won't need any additional memory space. Hence brute force approach will take:
Time complexity of O(N), Space complexity of O(1).
We will omit the code of this approach but a simple call for
inputArr.indexOf(searchKey) would give us the result.
Increasing efficiency
Since our array is sorted we can take advantage of that feature. If the array was not rotated, we could have used binary search to limit our time complexity to O(log(N)), so let's see if we can find a way to get close to that.
If we could spot the rotation point of our array, than we would have the minimum and maximum values determined. After that it would be easier to do a binary search on our array. To find the turning point, we inspect the array in a systematic way similar to what we do in binary search. While doing this, we will half our search area on each iteration which will give us a log(N) time complexity. We won't need any extra space correlated to out array size while doing this so our space complexity will be constant.
Time complexity of finding turning point O(log(N)). Space complexity of finding turning point O(1).
Let's see how it looks like.
const findTurningPoint = function(arr){
let start = 0;
let end = arr.length -1;
let mid = Math.floor((end-start)/2);
// We will keep track of start and end indexes and calculate mid based on them.
// First we will check if the array actually has a turning point. If not we will return -1
if(arr[start]<arr[mid] && arr[mid]<arr[end]){
// In a normal sorted array of unique elements:
// we would expect the start would be smaller than mid and mid be smaller then end
return -1;
}
// Now we will start adjusting our start and end points and recalculate mid on the go
// Or end condition is when our start hits mid or our mid hits end
while (start<mid && mid < end){
if(arr[start]> arr[mid]){
// if our start item is larger than the mid
// we know that our turning point is between them
// so we pull the end index to where mid is
// and recalculate mid
end = mid
mid = start + Math.floor((end-start)/2);
}else if(arr[mid]>arr[end] ){
// if our mid item is larger than the end
// we know that our turning point is between them
// so we pull the start index to where mid is
// and recalculate mid
start = mid;
mid = start+ Math.floor((end-start)/2);
}
}
// When this is over we would land on the turning point
// Note that turning point could be vague
// For this implementation our turning point lands on the maximum of the array
// The implementation can also be tweaked to land on the minimum of the array.
// To achieve that replace Math.floor with Math.ceil
return mid;
}Now that we can detect the turning point in a sorted array, we can continue with our search functionality. Given a search key with knowing the turning point of an array we can quickly check if the search key is between the max and the min of the array by comparing it to out turning point element and the element next to it. If it's out of these boundaries we will know that searchKey will not be there. If it is between those then we will have to perform our binary search algorithm on 2 parts of the array which are sorted within themselves and then return the result.
Since binary search has a time complexity of log(N), we will in return have a time complexity of log(c*N) + log((1-c)*N). c being a number between 0 and 1 (depending on the location of the turning point). We can expand that equation to log(c) + log(N) + log(1-c) + log(N). Since N>>c we can conclude that our time complexity will be scaling with log(N).
Time complexity O(log(N)).
Space complexity on the other hand depends on whether we implement binary search using recursion or iteration. If we use recursion, due to creating extra memory during recursive calls we will have a space requirement scaling with log(N), if we go with the iterative approach or space complexity will be constant.
Space complexity O(log(N)) or O(1) for recursive an iterative implementation.
Let's see how that looks like in code.
const binarySearchIterative = function(inputArr, searchKey){
if (inputArr.length == 0){
return -1;
}
if (searchKey < inputArr[0] || searchKey > inputArr[inputArr.length-1]){
return -1;
}
let start = 0;
let end = inputArr.length -1;
let mid = start + Math.floor((end-start)/2);
while(start<= end){
if(searchKey > inputArr[mid]){
start = mid+1;
}else if(searchKey < inputArr[mid]){
end = mid-1;
}else{
//we found the match so we return it.
return mid;
}
mid = start + Math.floor((end-start)/2);
}
return -1;
}
// Let's check how the recursive binarySearch looks like.
const binarySearchRecursive = function(inputArr, searchKey){
if (inputArr.length == 0){
return -1;
}
if (searchKey < inputArr[0] || searchKey > inputArr[inputArr.length-1]){
return -1;
}
return binSerRec(inputArr, searchKey, 0, inputArr.length-1);
}
const binSerRec = function(arr, key, start, end){
let mid = start + Math.floor((end-start)/2);
if (key == arr[mid]){
return mid;
}
if (start == end){
return -1;
}
if (key > arr[mid]){
return binSerRec(arr, key, mid+1, end);
}
if (key < arr[mid]){
return binSerRec(arr, key, start, mid-1);
}
return -1;
}Now that we have all our pieces, let's combine them to create the mechanism to search on rotated sorted arrays. We will use the iterative binary search in our final solution, but feel free to replace it with the recursive solution as well.
const searchRotatedArray = function(inputArr, searchKey){
const turningPoint = findTurningPoint(inputArr, searchKey);
if (turningPoint == -1){
// In this case we have a sorted array of 1 piece
return binarySearchIterative(inputArr, searchKey);
}else{
// Let's check if our key is within our boundaries
let maxIndex = turningPoint;
let minIndex = (turningPoint + 1)
if(searchKey > inputArr[maxIndex] || searchKey < inputArr[minIndex] ){
return -1;
}
// searchFirstPart
let firstPartSearch = binarySearchIterative(inputArr.slice(0, turningPoint+1), searchKey);
if (firstPartSearch != -1){
return firstPartSearch;
}
let secondPartSearch = binarySearchIterative(inputArr.slice(turningPoint+1, inputArr.length), searchKey);
if(secondPartSearch !=-1){
return secondPartSearch + turningPoint+1
}
return -1;
}
}Notice that if we find the searchKey in the first part, we return it, if we find it in the second part, we add the length of the first part to the result to give the index within the larger array.
Also note that we are passing an inputArr.slice() into our binarySearchIterative function which essentially copies that part of the array. Which in turn makes our space complexity O(N), we can overcome this issue by updating binarySearchIterative so that it takes the reference to the inputArray and also gets the start and end indexes to search within.
Feel free to checkout the complete code.
Please comment or dm me if you have other questions or remarks.
Until next time,
Stay all in!
Reha S.
Apr 25 2024