Search number in a rotated sorted array
Given : A rotated sorted array.
Objective : To search a number within the rotated sorted array using binary search.
Example of rotated sorted array.
The algorithm / idea to search the number in a rotated sorted array is as below
Locate (array, beg, end, target)
-
Case a)
If the array size is 0 the target would not exist in the array.
If beg > end, it means that the binary search is over and the target does not exist in the array.
If array[mid] == target, we return the index of the target that has now been found in the array using binary search. -
Case b)
From the example in the image it is evident that if ( array[0] <= arr[end] ), the array is already sorted. For a sorted array that has not been rotated, we use a simple binary search to find the number. -
Case c)
It is also evident that ( if array[0] <= array[middle] ), the left half of the array is already sorted.
If the target lies within the sorted left-half of the array we use a simple binary search to find it.
Else we recursive call Locate (array, mid+1, end, target) -
Case d)
Similarly if ( array[mid] <= array[end] ), the right half of the array is already sorted.
If the target lies within the sorted right-half of the array we use a simple binary search to find it.
Else we recursive call Locate (array, 0, mid-1, target)
Time Complexity : Log ( N ), as we use the binary search algorithm at the core for solving this problem.
C++ : Finding a number in a rotated sorted array
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Search{
public:
int BinSearch (vector<int>& arr, int beg, int end, int target) {
while (beg <= end) {
int mid = beg + (end - beg)/2;
if (arr[mid] == target)
return mid;
else if (arr[mid] > target)
end = mid-1;
else
beg = mid+1;
}
return -1;
}
int Locate (vector<int>& arr, int beg, int end, int target) {
if (arr.size() == 0 or beg > end)
return -1;
int mid = beg + (end - beg)/2;
int center = arr[mid];
if (center == target)
return mid;
// Sorted but not rotated.
/* 1 2 3 -> 3 1 2 -> 2 3 1 -> 1 2 3
Note : 2 1 3 is not a valid rotation */
if (arr[0] <= arr[end]) {
return BinSearch(arr, 0, end, target);
}
/* left-half is sorted */
if (arr[0] <= center) {
/* target possibly exists in the left-half */
if (arr[0] <= target and target <= center)
return BinSearch(arr, 0, mid-1, target);
/* Target exists in the right half */
else
return Locate(arr, mid+1, end, target);
}
/* right-half is sorted */
else if (center <= arr[end]) {
/* target possibly exists in the right-half */
if (center <= target and target <= arr[end])
return BinSearch(arr, mid+1, end, target);
/* Target exists in the left half */
else
return Locate(arr, 0, mid-1, target);
}
}
};
int main() {
Search S;
vector<int> arr = { 3, 4, 5, 6, 7, 8, -1, 0, 1, 2 };
cout << "Array : ";
for (const auto& i : arr) {
cout << i << " " ;
} cout << endl;
while (1) {
cout << "Search for : ";
int target;
cin >> target;
cout << "Position of " << target << " : " << S.Locate(arr, 0, arr.size()-1, target) << endl;
}
return 0;
}
Output
Array : 3 4 5 6 7 8 -1 0 1 2
Search for : 3
Position of 3 : 0
Search for : 4
Position of 4 : 1
Search for : 5
Position of 5 : 2
Search for : 6
Position of 6 : 3
Search for : 7
Position of 7 : 4
Search for : 8
Position of 8 : 5
Search for : 9
Position of 9 : -1
Search for : -1
Position of -1 : 6
Search for : 0
Position of 0 : 7
Search for : 1
Position of 1 : 8
Search for : 2
Position of 2 : 9
Search for : 10
Position of 10 : -1