Search in a Rotated Array

#include <bits/stdc++.h>
using namespace std;

// } Driver Code Ends

//Logic:Time complexity O(log(n))
/*
even if your mid at anywhere in array then,there is one thing for sure,either left half will be sorted or right half will be sorted.
if left half is sorted,then check key element in that range by comparing left half corner elements with key element
,if key is in range,again call for sorted range ie. low,mid-1
if left half is sorted,and key element is not in sorted range,call search for mid+1,high ie. right half

if right half is sorted,then check key element is that right half sorted range,if key in range call for mid+1,high
else call search for other half
*/
class Solution{
    public:
    int search(int arr[], int l, int h, int key){
        if(l<=h){
            int mid=(l+h)/2;
            if(arr[mid]==key) return mid;
            if(arr[l]<=arr[mid]){   //left half is sorted
                if(key>=arr[l] && key<arr[mid]){  //element present in sorted range
                    return search(arr,l,mid-1,key);
                }
                else{                               //element not present in sorted range
                    return search(arr,mid+1,h,key);
                }
            }
            else{                        //right half is sorted
                if(key>arr[mid] && key<=arr[h]) return search(arr,mid+1,h,key);  //element present in sorted range
                else return search(arr,l,mid-1,key);  //element not present in sorted range
            }
        }
        return -1;
    }
};