Normally there will be 2 comparisons that will be made in Binary Search Algorithm like
if(value > array[mid])
low = mid
else (value < array[mid])
high = mid
else (value == array[mid])
found the value
we have to reduce the number of comparisons made in the above code.
if(value > array[mid])
low = mid
else (value < array[mid])
high = mid
else (value == array[mid])
found the value
we have to reduce the number of comparisons made in the above code.
#include <stdio.h>
int array [ ] = { 0, 1,2,3,4,5,6,7,8,9 };
int bin_search(int val)
{
int low=0;
int high = sizeof(array)/sizeof(array[0]) - 1;
int mid;
while(low < high)
{
mid = (low+high)/2 ;
if(array[mid]<val)
low = mid+1;
else
high = mid;
}
if(array[low] == val)
{
return val; // found the value
}
else
return -1; // not found
}
int main()
{
int i;
for( i=0; i< 11; ++i)
printf("Return: %d\n", bin_search(i));
return 0;
}
* Your algorithm returns the value, not the index, which is not that useful
ReplyDelete* Your algorithm will read out of bounds of the array if the array is empty