Let n be the length of the array.
1. If the middle element is equal to its index return success.
2. If the middle element is greater than its index search the left
half, since all the elements to its right will be greater than or
equal to it and hence cannot be equal to their index.
3. Else search the right half since such an element will be probably
in the right half of the array.
C implementation
int binarySearch(int *arr,int n) //n is the size of the array
{
int l = 0, h = n - 1;
while(l <= n)
{
m = (l + h) / 2;
if(arr[m] == m)
return m;
else if(arr[m] > m)
h = m - 1;
else
l = m + 1;
}
return -1; //No such element exists
}
On Nov 3, 12:54 pm, lichenga2404 <lichenga2...@gmail.com> wrote:
> we are given a sorted array A[1...n] , composed of distinct integers,
> (the values can be negative). We want to determine if there is an
> index i such that A[i] = i.
>
> Give an O(logn) algorithm to solve this problem , and justify its
> correctness
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
