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