It would be logn+k, where k is the number of rotations right? But if there is 0 rotations, k would be equal to n, so worse case would be n?
static int binarySearchRotated(int[] arr,int key) {
int numberRotations=0;
boolean numRotationsFound=false;
while(!numRotationsFound && numberRotations<arr.length-1) {
if(arr[numberRotations] > arr[numberRotations+1]) {
numRotationsFound=true;
}
numberRotations++;
}
if(key>=arr[0] && key<=arr[numberRotations-1]) {
return binSearch(arr,key,0,numberRotations-1);
} else {
return binSearch(arr,key,numberRotations-1,arr.length-1);
}
}