# Search in Rotated Array

10.3 Search in Rotated Array: Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element in the array. You may assume that the array was originally sorted in increasing order.
EXAMPLE
Input:find 5 in { 15, 16, 19, 20, 25, 1, 3, 4, 5, 7,10, 14 }
Output: 8 (the index of 5 in the array)
• O(logN) time, with O(N) extra space (recursive)
• Algorithm: Find focal point in logn (minimum), preform binary search of left or right half.
// finding min element in O(logN)
int find_focal(vector<int> &ar, int low, int high) {
// not rotated
if (ar.begin()[1] < ar.end()[-1]) return 0;
else {
int middle = low + ((high - low) / 2);
// min element = next element is smaller || prev element is larger
if (ar.at(middle + 1) < ar.at(middle))
return middle + 1;
if (ar.at(middle - 1) > ar.at(middle))
return middle;
// search right
else if (ar.at(low) < ar.at(middle)) {
find_focal(ar, middle + 1, high);
}
else {
find_focal(ar, low, middle - 1);
}
}
}
int binary_search(vector<int> &ar, int low, int high, int target) {
if (high < low) return INT_MIN;
int middle = low + ((high - low) / 2);
if (ar.at(middle) == target) return middle;
// search right
else if (ar.at(middle) < target) {
binary_search(ar, middle + 1, high, target);
}
else {
binary_search(ar, low, middle - 1, target);
}
}
int find_rotated(vector<int> &ar, int findthis) {
if (ar.empty()) return INT_MIN;
// 1) Find focal point (min element)
int focal = find_focal(ar, 0, ar.size() - 1);
if (ar.at(focal) == findthis) return focal;
// search right
if (findthis > ar.at(focal) && findthis <= ar.end()[-1]) {
return binary_search(ar, focal + 1, ar.size() - 1, findthis);
}
// search left
else {
return binary_search(ar, 0, focal - 1, findthis);
}
}
int main() {
vector<int> ar = { 15, 16, 19, 20, 25, 1, 3, 4, 5, 7,10, 14 };
cout << find_rotated(ar, 5) << endl;
ar = { 20, 25, 1, 3, 4, 5, 7,10, 14, 15, 16, 17, 18 };
cout << find_rotated(ar, 5) << endl;
}