# Search number in a rotated sorted array

Binary Search looks for a value in a sorted array. It compares the middle number of the array with the searched value. If the middle number equals the searched value, the position of the middle number is returned. If the middle number is bigger, the left portion of the array is searched using the same logic (binary search), else the right portion of the array is searched using binary search.

Time complexity of the binary search algorithm for finding the smallest number in a sorted rotated array : Log ( N )

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

C++ : Binary search implementation for finding a number in a rotated sorted array in C++11

``````#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 <= arr[end]) {
return BinSearch(arr, 0, end, target);
}

/* left-half is sorted */
if (arr <= center) {
/* target possibly exists in the left-half */
if (arr <= 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 of binary search for finding a number in a rotated sorted array. Implemented in C++11.

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