A rotated array is a combination of two sorted array. so let’s find a pointer on where the array is rotated. Then let’s split the input array into two sorted array. Now if the search key is present in left array, we can pass the binary search function for left array or vice versa.

 

binrotsort

Code:

int binarySearch(int [] in, int x){

int low =0, high = in.length-1;

while (low <= high){

int mid = (low + high)/2 ;

if(x > in[mid])

low = mid + 1 ;

else if(x < in[mid])

high = mid – 1;

else

return mid;

}

return -1;

 

}

 

int binarySearchRotate(int []in, int x){

int low =0, high = in.length-1;

int start = in[0], pointer=0, k=1, val = -1;

 

//Loop to find the pointer of where the array is rotated

while(start < in[k])

pointer = k++;

pointer++;

 

//Split the array into two and store it on left and right array based on the pointer value like merge sort

 

//Store 0 to pointer in left array

int left[] = new int[pointer];

for(int i=0; i<left.length;i++)

left[i]=in[i];

 

//Store Pointer to input array length on right array

int right[] = new int[in.length-pointer];

for(int j=pointer;j<in.length;j++)

right[j-pointer] = in[j];

 

//If search value is from 0 to pointer-1, pass binary search function for left array

if((x >= in[low]) &&(x <= in[pointer-1]))

val = binarySearch(left,x);

 

//If search value is from pointer to length of input array, pass binary search function for right array

else if((x >= in[pointer]) &&(x <=in[high]))

val = pointer + binarySearch(right, x);    //Increment the final output

 

return val;

}

 

Close Bitnami banner
Bitnami