{"id":6788,"date":"2025-02-01T00:01:03","date_gmt":"2025-02-01T08:01:03","guid":{"rendered":"https:\/\/c-for-dummies.com\/blog\/?p=6788"},"modified":"2025-01-11T10:06:50","modified_gmt":"2025-01-11T18:06:50","slug":"finding-structures-with-the-bsearch-function","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=6788","title":{"rendered":"Finding Structures with the bsearch()<\/em> Function"},"content":{"rendered":"

It’s easy to explain the bsearch()<\/em> function when using integers. One step up is to search for strings, covered in last week’s Lesson<\/a>. At the pinnacle of insanity, however, is searching through an array of structures.
\n
\nThe bsearch()<\/em> function locates a structure based on one of its members. The issues are setting the key as a structure (something I had to figure out), and coding the compare()<\/em> function to properly manipulate the structures.<\/p>\n

To test the function, I use this structure, potus<\/em>:<\/p>\n

struct potus {
\n    int index;
\n    char *name;
\n};<\/code><\/p>\n

And this array of potus<\/em> structures, named presidents[]<\/code>:<\/p>\n

struct potus presidents[] = {
\n    { 1, \"Washington\" }, { 2, \"Adams\" }, { 3, \"Jefferson\" },
\n    { 4, \"Madison\" }, { 5, \"Monroe\" }, { 6, \"Adams\" }
\n};<\/code><\/p>\n

You can search this array for any member of the structure — but only one member. You cannot search for an entire structure as they must be sorted. In a database, sorting is based upon a specific key. For this example, I’m sorting based on the name<\/code> string. Even so, the search key must be another structure; it cannot be a string by itself.<\/p>\n

The following code shows how to search for a specific structure based on its name<\/code> (string) member.<\/p>\n

2025_02_01-Lesson.c<\/a><\/h3>\n
\r\n#include <stdio.h>\r\n#include <stdlib.h>\r\n#include <string.h>\r\n\r\nstruct potus {\r\n    int index;\r\n    char *name;\r\n};\r\n\r\nint compare(const void *a, const void *b)\r\n{\r\n    char *name1 = ((struct potus *)a)->name;\r\n    char *name2 = ((struct potus *)b)->name;\r\n    return( strcmp(name1,name2) );\r\n}\r\n\r\nint main()\r\n{\r\n    struct potus presidents[] = {\r\n        { 1, \"Washington\" }, { 2, \"Adams\" }, { 3, \"Jefferson\" },\r\n        { 4, \"Madison\" }, { 5, \"Monroe\" }, { 6, \"Adams\" }\r\n    };\r\n    struct potus *r,*key;\r\n    char input[32];\r\n    int size;\r\n\r\n    \/* obtain array size *\/<\/span>\r\n    size = sizeof(presidents)\/sizeof(presidents[0]);\r\n\r\n    \/* obtain input *\/<\/span>\r\n    printf(\"President: \");\r\n    scanf(\"%s\",input);\r\n    \/* the key must be a structure to match\r\n       the index member need not be set *\/<\/span>\r\n    \/* allocate storage for both the structure\r\n       as well as the name *\/<\/span>\r\n    key = malloc( sizeof(struct potus) );\r\n    key->name = malloc( sizeof(char) * 32 );\r\n    if( key== NULL || key->name==NULL )\r\n    {\r\n        fprintf(stderr,\"Unable to allocate structure\\n\");\r\n        exit(1);\r\n    }\r\n    strcpy(key->name,input);\r\n\r\n    \/* sort the list *\/<\/span>\r\n    qsort(presidents,size,sizeof(struct potus),compare);\r\n\r\n    \/* locate a value *\/<\/span>\r\n    r = bsearch( key, presidents, size, sizeof(struct potus), compare );\r\n    if( r!=NULL )\r\n        printf(\"Key %s found!\\n\",r->name);\r\n    else\r\n        printf(\"Key %s not found.\\n\",key->name);\r\n\r\n    return 0;\r\n}<\/pre>\n
The array’s size is obtained by dividing the total array size, sizeof(presidents)<\/code>, by the size of a single member, sizeof(presidents[0])<\/code>:<\/p>\n
size = sizeof(presidents)\/sizeof(presidents[0]);<\/code><\/p>\n
The next step is to allocate the key<\/code> structure, which is the same type of structure used in the array. Also — and this is important — the name<\/code> member of the structure must also be allocated:<\/p>\n
key = malloc( sizeof(struct potus) );
\nkey->name = malloc( sizeof(char) * 32 );<\/code><\/p>\n
(An issue might exist if the key<\/code> allocation fails before trying key->name<\/code>. In my example I test both together, though they should be tested separately to create more secure code.)<\/p>\n
Once allocated, user input (stored in variable input<\/code>) is copied into the key<\/code> structure’s name<\/code> member:<\/p>\n
strcpy(key->name,input);<\/code><\/p>\n
You need not assign a value to the index<\/code> member as it’s unused, so whatever garbage in memory is okay.<\/p>\n
Next the qsort()<\/em> function sorts on the array based upon the name<\/code> member. The compare()<\/em> function uses two local pointers to obtain the name strings, then the strcmp()<\/em> function is used in the return<\/em> statement to cough up the results:<\/p>\n
char *name1 = ((struct potus *)a)->name;
\nchar *name2 = ((struct potus *)b)->name;
\nreturn( strcmp(name1,name2) );<\/code><\/p>\n
Finally, bsearch()<\/em> is called. But note that no ampersand prefixes the key<\/code> argument as it’s already an address:<\/p>\n
r = bsearch( key, presidents, size, sizeof(struct potus), compare );<\/code><\/p>\n
Here’s a sample run:<\/p>\n
President: Jefferson
\nKey Jefferson found!<\/code><\/p>\n
As I wrote earlier, it took me a while to figure out that the first argument in the bsearch()<\/em> function must be of the same data type (the potus<\/em> structure) as the items in the array. I tried using a string again and again, but the program crashed merrily. Only when I looked at the compare()<\/em> function did I realize that the data types must match for the code to run successfully.<\/p>\n","protected":false},"excerpt":{"rendered":"
Things can get crazy fast when searching through an array of structures. Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-6788","post","type-post","status-publish","format-standard","hentry","category-main"],"_links":{"self":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/6788","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=6788"}],"version-history":[{"count":6,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/6788\/revisions"}],"predecessor-version":[{"id":6814,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/6788\/revisions\/6814"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=6788"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=6788"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=6788"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}