## Saturday, May 8, 2010

### What is Binary Search and How to implement in C

Binary search is search mythology in a sorted list. In this process first find the middle element of list and if it is equal to the middle element its done. other wise if number is greater than the middle number search in next half otherwise search in first half with same pattern(Find the middle  element and compare).

Here is Binary search implementation in C.

#include <stdio.h>

int binary_search(int array[], int value, int size)
{
int found = 0;
int high = size, low = 0, mid;

mid = (high + low) / 2;

printf("\n\nLooking for %d\n", value);

while ((! found) && (high >= low))
{
printf("Low %d Mid %d High %d\n", low, mid, high);

if (value == array[mid])
found = 1;
else if (value < array[mid])
high = mid - 1;
else
low = mid + 1;

mid = (high + low) / 2;
}
return((found) ? mid: -1);
}

void main(void)
{
int array, i;

for (i = 0; i < 100; i++)
array[i] = i+20;

printf("Result of search %d\n", binary_search(array, 44, 100));
printf("Result of search %d\n", binary_search(array, 77, 100));

}

1. This algorithm is WRONG. Try searching the array {1} for the value 2. (so size = 1). First iteration: low = 0, high = 1, mid = 0. Second iteration: low = 1, high = 1, mid = 1. Then you get a segfault when you try to access array[mid].

2. Yes there is a loop hole. you can add a line after calculating mid.

if(mid >= size)
break;