Searching An Element In The Rotated Sorted Array
Introduction
Before understanding the solution of the problem let’s understand what an array is.
What is an Array?
An array is the basic Data Structure that contains items of similar data types.
There is always an ordering amongst the position of the element.
It can be accessed with the help of the indices. And most of the modern programming languages have the support of a 0-indexed array.
Problem Statement
Given an Array of rotated sorted elements arr[] of size n and elements can be rotated by k times And given the target value. We need to find whether the element of a target is present on an array or not. If it is present then return the index i of that element else return -1 which indicates that element is not present.
We may assume that the elements are distinct in the array.
Example 1
Input = arr[5,6,1,2,3,4] target = 6 Output = 1 Explanation = Element Found at index 1. |
Example 2 -
Input = arr[8,9,10,12,13,6,7] target = 7 |
Example 3-
Input = arr[1,2] target = 3 |
Solution-
The very first approach or naive approach we can follow is that we can simply traverse the whole array sequentially and search for the element.
Algorithm -
Start
Loop i = 1 to n:
If arr[ i ] = target
Return index i
Else
Continue checking the next element
Return -1
Stop
C++ Implementation
#include <iostream>
#include <vector>
using namespace std;
// search method will return the index of the element
int search(vector<int> arr, int target){
int i = 0;
//Initializing the index for traversal and starting a loop
//and goes up to the last element of an array.
while(i < arr.size()){
if(arr[i] == target){
return i; //Returning the index if element found
}
i++;
}
return -1;
//Returning index -1 when element is not found.
}
int main() {
vector<int> arr{5,6,1,2,3,4};
//Setting the target value.
int target = 6;
//Calling the search method with an argument of array and
//target value and function will return the answer.
int index = search(arr, target);
if(index == -1){
cout << "Element doesn't exist";
}else{
cout << "Element found at index = " << index;
}
return 0;
}Output- Element found at index = 1 |
Try C++ Compiler from InterviewBit
Explanation -
Check if the target value matches the current index value of the array. If not found then go to the next index and follow the same.
If the target element is found in the array then return the current index.
Else return -1 if not matches in the entire array.
Time Complexity Analysis -
We are traversing the entire array element once. So the number of iterations depends on the input size. So the time complexity in the Worst case if O(n) – If Element Not Found.
If the element is found at the first index then in that case the time complexity will be O(1). – As the Best Case.
Now for the Average case when an element is found then it can be found between the first to last index so time complexity will be O(n) – If Element found.
Space Complexity Analysis -
In the algorithm, we are only taking index as extra space which is not dependent on input size. So the space complexity will be O(1).
Optimization -
Approach 1-
The Algorithm we designed will take O(n) time. Which is not very efficient. So can we somehow reduce the time complexity and make the algorithm more efficient.
We know that searching can be done on the sorted array is in O (log n) time. But here the array is not exactly sorted. But it is rotated by some k times.
Now let's take an example of the array = [5, 6, 7, 1, 2, 3, 4].
If we analyze that then we will find that the array is sorted into two parts. And both part is sorted. So can we somehow find that element that is at the max or the peak element?
If we found the peak element in the array then we can divide the array into two parts. And after that, we can apply the Binary search on both the subarray and be able to search for an element in logarithmic time.
But the task is how we can find the peak element in an array -
Finding Peak Element of Array-
Peak element is that element in the array which is greater than both of its left and right element.
We need to find the peak element in an array with O(log n) time complexity.
So we can search that element in an array which have the property-
Greater than its left element and also greater than the right element.
If the array has only one element then it is a peak element.
So, Algorithm for finding peak elements in an array includes certain steps to be followed:-
Algorithm for peak element -
Find the mid index.
if mid > low and value at mid < value at mid -1, then mid - 1 will be the peak element so return mid - 1 index.
If mid < high and value at mid > value at mid + 1, then that will be the peak element so return mid-index;
Now if the value at index low is greater than or equal to the value at mid-index then the peak element must exist between (low to mid - 1) subarray so again calculate mid in respect with the left subarray and go to step 2;
If the step 4 condition fails then the element must exist between the right sub-array from (mid+1 to high). So calculate mid in respect to that and go to step 2.
In the algorithm, we need to check a corner case that whether there is only a single element then that is the peak element so will return either low or high index value.
Note: - This algorithm returns -1 as an index if found that the element is already sorted.
Example:-
Initially, in the first iteration, we found that the mid element is 1. And it is not the peak element so we check for the greater value which exists on what side of the mid.
It is found that the element at mid-1 is the peek so it will return mid-1.
After finding the peek element index now we can split the array into its two-part and both the subarray will be sorted based on the peek element index.
Now we can apply the binary search algorithm on both the subarray based on a check that the target value exists on which subarray by checking the range of elements of both subarrays.
Steps for searching on subarrays-
If the target value is in the range from 0 to peek index then apply binary search on this sub-array.
Else apply the binary search on the other side of the subarray from peak +1 to the end of the subarray based on the range check.
Algorithm-
Peak <- findPeekIndex()
If target is in range 0 to peak-1
Then Binary Search on low = 0 to high = peak-1;
Else if target is in range peek to end of array
Then Binary Search on low = peek to high = end of the array
Return result returned from binary search
Note: - Binary Search will return the index of the target value is found in the array else it will return -1.
Explanation-
At the very first step, we are finding a peak element on an array because the peak element helps in splitting it into the two different sorted subarrays such that we can apply the binary search to make the solution efficient.
After finding the peak element, we are searching for the target element based on the ranges of subarrays.
Now we can apply binary search on the Left subarray as the target value exists in the range of the left subarray. And the right subarray will be pruned.
C++ Solution
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int findPeak(vector<int> arr, int low, int high)
{
if(high == low) // Corner case when only single element is present.
return low;
while(low < high){
//calculating the mid index
int mid = (low + high) / 2;
//checking if the element of mid+1 is the peak
if (mid < high && arr[mid] > arr[mid + 1])
return mid;
//checking if the element of mid-1 is the peak
else if (mid > low && arr[mid] < arr[mid - 1])
return (mid - 1);
//checking if element exists on the left side of array from mid then
//search on left side
else if (arr[low] >= arr[mid])
high = mid - 1;
//checking if element exists on right side of array from mid
//then search on right
else
low = mid + 1;
}
return -1; // returning -1 if element is completely sorted
}
int binarySearch(vector<int> arr, int low, int high, int target){
while (low <= high){
//calculating mid index
int mid = low + (high - low)/2;
//if the mid index is the target then return index.
if (arr[mid] == target)
return mid;
// if the mid-value is less than target then go to the right subarray
if (arr[mid] < target)
low = mid + 1;
// Otherwise go to the left subarray
else
high = mid - 1;
}
return -1; //Return -1 if element not found.
}
int main() {
vector<int> A{5,6,1,2,3,4};
int target = 4, n = A.size()-1;
//Calling find peak method which returns the index value of peak element
int peak = findPeak(A, 0, n);
int index;
//Checking value of peak. (if -1 then the array is completely sorted).
if(peak == -1){
//So binary search on the entire array.
index = binarySearch(A, 0, n, target);
}else{
//Applying binary search according to the range that exists
//on subarrays (0 - peak || peak+1 - n).
if(target >= A[0] && target <= A[peak])
index = binarySearch(A, 0, peak, target);
else if(target >= A[peak+1] && target <= A[n])
index = binarySearch(A, peak+1, n, target);
if(index == -1){
cout << "Element dont exist";
}else{
cout << "Element found at index = " << index;
}
}
return 0;
}Output : Element found at index = 5 |
Time Analysis-
We are finding the peak element first to divide the array into two sorted subarrays. And this is done in O(log n) time.
And next, we are applying binary search in the subarray of either left or right which takes O(log n) time as binary search is applied.
So overall time complexity is - O(log n) + O(log n) which is nothing but the order of O(log n) for all in best, average, and worst cases.
Space Analysis-
We are not taking any extra space for getting the value except for some index variables and it is not dependent on the input size. So the Space complexity is O(1).
Approach 2-
If we analyze approach 1 then we find that we are traversing the array twice -
Finding peek element.
Binary the search.
So can we somehow ignore finding the peak element and search the element in a single pass?
Let’s understand -
We know that the array elements are sorted but are rotated by some k times.
So if we find that the from the middle, which side of the array is sorted, and does the element exists between the subarray or not.
Like in approach 1 we have checked if the element exists between the range of left and right subarray. So can we apply the same strategy here also for checking?
Example:-
We check if the element from low to the mid index is sorted or not by just comparing the low index value with the mid index value. And we find that element is not sorted which means the element from mid-index to the high-index will be sorted.
So we will check that part if the target element exists in that range or not. If the target element exists in the right subarray then we can search on that portion else we can search on the left subarray.
And again follow the same for the subarray.
Algorithm-
low = 0, high = n
Loop utill low <= high
mid = (low+high)/2
if mid value == target then return the mid index
if low value is <= mid value
if target exists in the range from (low to mid) then high = mid-1
else low = mid + 1
else
if target exists in range from (mid+1 to high) then low = mid+1
else high = mid-1
Return -1 after the loop terminates and the element didn’t found.
Explanation-
Given an array, we are finding the mid element on each iteration and checking that is the left subarray is sorted or not? if sorted then do the target values exist in the range or not? Because if the subarray is sorted and the value exists between the a=subarray then we proceed to search on the subarray.
Otherwise, we check the element range on the side that if the element contains in range or not. And then proceed to the appropriate subarray accordingly.
Example 1- Given an array A = [6, 1, 2, 3, 4, 5] target = 6
In the first iteration - A[low] <= A[mid] == false { 6 <= 2}. So check for right subarray and check for range exists between A[mid] to A[high].
In the 2nd Iteration, the target value is found at the mid-index so the mid index will be returned.
C++ Solution-
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int search(vector<int> A, int target) {
int low = 0, high = A.size()-1, mid;
while(low <= high){
//Calculating mid
mid = (low + high)/2;
//Returning mid if target found on mid
if(A[mid] == target) return mid;
//Checking if left subarray is sorted?
if(A[low] <= A[mid]){
//Checking if elements exist between low to mid
if(target >= A[low] && target <= A[mid])
//if found that element exists in the range so search
//in the left subarray
high = mid-1;
else
//if element don't exist between range the search on
//right sub array
low = mid+1;
}else{
// checking if target exists in the right subarray range
if(target >= A[mid] && target <= A[high])
//If element exist in range then search on right subarray
low = mid+1;
else
//If elements don't exist in the right subarray then search
// on left subarray
high = mid-1;
}
}
return -1; //return -1 if element dont exist in array.
}
int main() {
vector<int> A = {6,1,2,3,4,5};
int target = 6;
int index = search(A, target);
if(index == -1){
cout<< "Element dont exist";
}else{
cout<< "Element found at index = " << index;
}
return 0;
}Output : Element found at index = 0 |
Time Analysis-
Here in this algorithm, we are checking the element that exists in range and proceeding to the appropriate subarray accordingly. And also we prune the subarray for every iteration which doesn’t contain the target value.
So we are reducing subarray size on each iteration half so the time complexity is
O(log n) for worst ad average case.
And for best case time complexity is O(1) if the target value exists in the middle.
Space Analysis-
This solution also doesn’t require any additional space except the index pointers which don’t depend on input size. So Space complexity is - O(1) Constant.
Conclusion
For the given problem many solutions can be applied to solve the problem but the most efficient one that takes less execution time and space.
So arriving at the best solution is done sequentially on each step and analysis of the unnecessary computation that is happening such that we can prune it to make the solution efficient.
This problem can easily be transformed from the linear time complexity to the logarithmic time complexity using some modified approach of binary search.