### Logic :

- Find the middle element of array.

Mid = (low+high) /2

- Check for the sorted portion of array(Note: There will be always a sorted portion if you divide this array in two parts ) either array[low] to array[mid] or array[mid] to array[high].
- If array[low] to array[mid] sorted and key is also present then recur array[low] to array[mid]. Otherwise recur array[mid] to array[high].
- .Otherwise, if array[mid] to array[high] sorted and key is present within this range then recur array[mid] to array[high].
- Otherwise, recur array[low] to array[mid].

The base condition of recursion is

```
if (input_Arr[mid] == search_key)
return mid;
```

This is the small example:

**15, 16, 17, 18, 19**, 20, 11, 12, 13, 14

Lets take the key as **18**.

Middle = (low + high) /2, so middle element here is 19.

Now, check on which side key lies. Left side or right side and recur it into that direction.

Here the element must be on left side of the middle element. So, again do recursion till it reaches to the key element.

Check here for another solution of this problem.

Time complexity of this problem is** O(logn)**

Another corner case example is **9,10,11,1,2,3,4,5,6,7,8**, please see this example in code and try to understand, comment if there is doubt in logic.

### Search element in sorted rotated array code

```
//searching element in given sorted rotated array.
//all the elements in the array should be distinct
// Time complexity of the code is O(logn).
#include "iostream"
using namespace std;
int find_element_fun(int * input_Arr, int low, int high, int search_key){
if (low > high)
{
cout << " Value Not found " << endl;
return -1;
}
//finding the mid element
int mid = (low + high) / 2;
//base case condition
if (input_Arr[mid] == search_key)
return mid;
// checking for the sorted array.
if (input_Arr[low] <= input_Arr[mid])
{
if (input_Arr[low] <= search_key && input_Arr[mid] >= search_key)
return find_element_fun(input_Arr, low, mid - 1, search_key);
return find_element_fun(input_Arr, mid + 1, high, search_key);
}
if (input_Arr[mid] <= search_key && input_Arr[high] >= search_key)
return find_element_fun(input_Arr, mid + 1, high, search_key);
return find_element_fun(input_Arr, low, mid - 1, search_key);
}
int main(){
//int input_Arr[] = { 15, 16, 17, 18, 19, 20, 11, 12, 13, 14 };
int input_Arr[] = {9,10,11,1,2,3,4,5,6,7,8};
int search_Key = 11;
//cin >> search_Key;
int length = sizeof(input_Arr) / sizeof(input_Arr[0]);
cout << find_element_fun(input_Arr, 0, length-1, search_Key) << endl;;
}
```

http://www.waytocrack.com/forum/394/search-pivot-element-in-a-rotated-sorted-array