C/Data Structure Algorithm/Search

Binary search:bsearch in stdlib.h

<source lang="cpp">

1. include <stdio.h>
2. include <stdlib.h>

int values[] = { 1 , 2 , 3, 4 , 9 , 10 }; int compare (const void * a, const void * b) {

 return ( *(int*)a - *(int*)b );

} int main () {

 int *pos;
 int key = 9;
 
 pos = (int*) bsearch (&key, values, 6, sizeof (int), compare);
 
 if ( pos != NULL )
   printf ("%d is in the array", *pos);
 else
   printf ("%d is not in the array", key);
 
 return 0;

}

      </source>

The Binary search

<source lang="cpp">

int binary_search(char *items, int count, char key) {

 int low, high, mid;
 low = 0; high = count-1;
 while(low <= high) {
   mid = (low+high)/2;
   if(key < items[mid]) high = mid-1;
   else if(key > items[mid]) low = mid+1;
   else return mid; /* found */
 }
 return -1;

}

      </source>