 |
bsearch |
Function* (tigcc.a) |
Binary search.
bsearch searches a table (array) of NoOfElements elements in memory, and returns
the address of the first entry in the table that matches the search key. Because this is a
binary search, the first matching entry is not necessarily the first entry in the table.
If no match is found, bsearch returns NULL.
NoOfElements gives the number of elements in the table.
Width specifies the number of bytes in each table entry.
BasePtr points to the base (0-th element) of the table to be sorted.
Key is a pointer to the search key.
cmp_func, the comparison function, accepts two arguments,
elem1 and elem2, each a pointer to an entry in the table.
The comparison function compares each of the pointed-to items (*elem1 and
*elem2), and returns a short integer based on the result of the comparison:
- If *elem1 < *elem2, cmp_func should return an integer < 0.
- If *elem1 == *elem2, cmp_func should return 0.
- If *elem1 > *elem2, cmp_func should return an integer > 0.
Here is a complete example of usage (called "Binary Search"):
// Search integer values using a binary search.
#define USE_TI89 // Compile for TI-89
#define USE_TI92PLUS // Compile for TI-92 Plus
#define USE_V200 // Compile for V200
#define OPTIMIZE_ROM_CALLS
#define MIN_AMS 100 // Compile for AMS 1.00 or higher
#define SAVE_SCREEN // Save/Restore LCD Contents
#include <tigcclib.h> // Include All Header Files
// Comparison Function
CALLBACK short int_comp(const void *a, const void *b)
{
return (*(const short*)a) - (*(const short*)b);
}
// Main Function
void _main(void)
{
short list[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
short i;
short font;
void *p;
font = FontGetSys();
FontSetSys(F_4x6);
clrscr ();
for (i = -1; i < 11; i++) {
p = bsearch (&i, list, sizeof(list)/sizeof(list[0]), sizeof (list[0]), int_comp);
if (p == NULL) {
printf ("%d not found\n", i);
}
else {
printf ("%d is at index %lu\n", i, ((void *)p - (void *)list)/sizeof(list[0]));
}
}
FontSetSys(font);
ngetchx ();
}
Note: if speed matters, create a bsearch() routine in your program, and inline the comparison
function and element copy/swap codes. Your routine will be significantly faster and smaller that way.
See also: qsort