2016年10月9日星期日

Find a Fixed Point in a given array

Find the number in the array which is equal to its index. Return -1 if not found.

if duplicate exists, the worst case is O(n);


no duplicate:

 int binarySearch(int arr[], int low, int high)  
 {  
   if(high >= low)  
   {  
     int mid = (low + high)/2; /*low + (high - low)/2;*/  
     if(mid == arr[mid])  
       return mid;  
     if(mid > arr[mid])  
       return binarySearch(arr, (mid + 1), high);  
     else  
       return binarySearch(arr, low, (mid -1));  
   }  
   /* Return -1 if there is no Fixed Point */  
   return -1;  
 }  

没有评论:

发表评论