C/Data Structure Algorithm/Search
Binary search:bsearch in stdlib.h
<source lang="cpp">
- include <stdio.h>
- 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>