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)