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.

Why is mid calculated as mid = beg + (end-beg)/2 ?

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
``````