# Search Element In a Rotated Sorted Array (C++)

Question : You are given an integer array .The given array is sorted but it is rotated . For example , [2,3,4,1,2] is sorted and rotated .You need to find the given element in the array and return the index , if it isnot present return -1.

```Input  : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};
key = 3
Output : Found at index 8```

Brute Solution :
We can do it easily using linear search . Start traversing the array from first element and check if your current element matches with given , if you get a match , then return the index else return -1.
Pseudo Code:
for(i=0 to n-1){
if(arr[i]==key){
return i;
}
}

Time complexity : O(n)
Space Complexity : O(1)

Optimal Solution :
To optimize the above method , we will be using Binary Search here though the array is not completely sorted .We will make some observations in order to use binary search here .

Take a low pointer at 0th index and high pointer at (n-1)th index .Now take a mid pointer as mid=low+(high-low)/2 .
If key is present in mid pointer simply return the mid .

If not then , first check if arr[low…mid] is sorted , to do so simply you do : if(nums[low]<=nums[mid]) , now if it is sorted ,
then check , if(key>=nums[low] and key<=arr[mid]) , now if it is true your key actually lies between arr[low] and arr[mid] because you know it is sorted , so you can simply eliminate the right part by doing high=mid-1.

if your key doesnt lies between arr[low] and arr[mid] then simply eliminate left half , so make low=mid+1 .

Now say your left half isnot sorted then your right half must be sorted , arr[mid….high] ,so follow the same logic in this case also . If key lies between mid to high ,
if(key>=nums[mid] and key<=nums[high]) then eliminate your left half else eliminate your right half .

Code :
C++
Function to find the given key :

`int search(vector<int>& nums, int target) {`

``````    int low=0;
int high=nums.size()-1;

while(low<=high)
{
int mid=low+(high-low)/2;

if(nums[mid]==target)
{
return mid;
}

if(nums[low]<=nums[mid])
{
if(target>=nums[low] and target<=nums[mid])
{
high=mid-1;
}
else
{
low=mid+1;
}
}
else
{
if(target>=nums[mid] and target<=nums[high])
{
low=mid+1;
}
else
{
high=mid-1;
}
}
}

return -1;

}``````

Time Complexity : O(logn)
Space Complexity : O(1)