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;
}
没有评论:
发表评论