Wednesday, December 03, 2008

Reduce the comparisons in Binary Search

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.

#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;
}

1 comment:

  1. * Your algorithm returns the value, not the index, which is not that useful
    * Your algorithm will read out of bounds of the array if the array is empty

    ReplyDelete