Searching an Element in Rotated Sorted Array

One of my friend was ask to devise an algorithm to search a number on a rotated sorted array. Well, we can always do a linear search. But that cannot be optimal we are neglecting the fact that the array was once sorted. The array is still sorted but has been rotated at some point. So, if we could find the rotation point, we could still use binary search to find the number.


On further analysis, it can be seen that we can apply a modified binary search on the array without even finding the pivot element. We can always divide the array into two halves using the middle element. It can be seen that one of two halves of the array will be strictly sorted. If the number that has to be searched lie within the sorted-half range, we can simply apply binary search on the sorted half. However, if the number is on the other half of the array, we can apply the above procedure on the second half of the array breaking it into further halves and analyzing.

Let us start by taking an example array: 7 8 9 1 2 3 4 5 6. The mid element of the array is 2. Dividing the array over 2, we get two sub array: 7 8 9 1 and 3 4 5 6, of which 3 4 5 6 is sorted and we can apply binary search over it. However, if the number to be search is out of sorted range, the sub array 7 8 9 1 can be further divided and analyzed using the above algorithm.

C Code:

 # include <stdio.h>  
 # include <malloc.h>  
 int binary_search(int ptr[],int first,int last,int num);  
 int rotated_binary_search(int ptr[],int size,int num);  
 int main()  
 {  
      int size,num,i;  
      int *ptr;  
      printf("Enter the size of array :-");  
      scanf("%d",&size);  
      printf("Enter the number to be searched :-");  
      scanf("%d",&num);  
      ptr = (int*)malloc(size*sizeof(int));  
      for(i=0;i<size;i++)  
           scanf("%d",&ptr[i]);  
      int index =     rotated_binary_search(ptr,size,num);  
      printf("The index is : %d",index);  
      return 0;  
 } 
 int rotated_binary_search(int ptr[],int size,int num)  
 {  
      int mid=0,index=-1,first=0,last = size-1;  
      while(first<=last)  
      {  
           mid = (first+last)/2;  
           if(num==ptr[mid])  
           {  
                index=mid;  
                break;  
           }  
           else   
           {  
                if((ptr[first] <= ptr[mid]))  
                {       
                     if(num <= ptr[mid] && num >= ptr[first])  
                     {  
                          index=binary_search(ptr,first,mid-1,num);  
                          break;  
                     }  
                     else  
                          first=mid+1;  
                }  
                else if((ptr[last]>ptr[mid]))  
                {  
                     if(num <= ptr[last] && num >= ptr[mid])  
                     {  
                          index=binary_search(ptr,mid+1,last,num);  
                          break;  
                     }  
                     else  
                          last=mid-1;  
                }  
           }  
      }  
      return index;  
 }
 int binary_search(int ptr[],int first,int last,int num)  
 {  
      int mid=0,index=-1;  
      while(first<=last)  
      {  
           mid = (first + last)/2;  
           if(num == ptr[mid])  
           {  
                index = mid;  
                break;  
           }  
           else if(num < ptr[mid])  
                last = mid -1;  
           else if(num > ptr[mid])  
                first = mid +1;  
      }  
      return index;  
 }