Searching an Element in a Rotated Sorted Array

Reducing the search space by half : O(lgn)


public static void search(int[] a,int element){
int i=0,j=a.length-1;
boolean found=false;;
while(i<=j){
int middle = (i+j)/2;
if(a[middle]==element){
found=true;
System.out.println("Element is found @ index :" +middle+ " of rotated array");
}


if(a[i] < a[middle]){ // first half is in increasing order
if(a[i] <= element && element < a[middle])
j=middle-1;
else
i=middle+1;
}

else {
if(element > a[middle] && element <= a[j])
i=middle+1;
else
j=middle-1;

}
}

if(!found)
  System.out.println("Given element not found");
}