C / STANDARD LIBRARY TOUR
Sorting and searching with qsort and bsearch
Sort any array with qsort and look elements up with bsearch by writing comparators that handle void pointers, element widths and NULL results correctly.
What you will learn
- Write comparators taking two const void * and cast them to the element pointer type
- Return (x > y) - (x < y) instead of x - y so wide values cannot overflow
- Pass sizeof arr[0] as the element size and check bsearch's return against NULL
- Search only with the same comparator the array was sorted by, or hits become NULL
Understanding Sorting and searching with qsort and bsearch
qsort and bsearch are the standard library's answer to a language without generics: instead of knowing your element type, they take the address of the first element, how many elements there are, how many bytes one element occupies, and a function that can order two of them. qsort rearranges the array by copying that many bytes at a time, so the size argument must be the true element width, and sizeof base[0] is the form that stays correct when the element type later changes. Everything type-specific lives in the comparator, which is why the comparator is handed const void * pointers into the array rather than the values themselves.
A comparator returns a negative value when its first argument sorts before its second, zero when they are equivalent, and a positive value otherwise; the magnitude is ignored, only the sign is read. The tempting *(const int *)a - *(const int *)b is wrong for wide ranges because the subtraction itself can overflow and flip sign, while (x > y) - (x < y) yields -1, 0 or 1 with no arithmetic risk. The ordering also has to be self-consistent: if cmp(a,b) is negative then cmp(b,a) must be positive, and equivalence must be transitive, otherwise the call is undefined behaviour and real implementations can walk off the end of the array.
bsearch takes those same four arguments plus a pointer to the key, and it halves the remaining range based on the sign the comparator returns. That only works when the array is already ordered by that same comparator, so sorting ascending and then searching with a descending comparator, or searching an array you forgot to sort, is undefined behaviour that typically shows up as a NULL return for a value that is plainly present. On success you get a pointer to some element that compares equal, and which one is unspecified when duplicates exist, so subtract the base pointer to turn it into an index; on failure you get NULL, which must be tested before any dereference.
qsort is not required to be stable, and glibc, musl and MSVC do not agree on how equal-comparing elements end up ordered, so put a tiebreaker member into the comparator whenever the relative order of ties is part of your expected output.
<stdio.h>
<stdlib.h>
static int cmp_int(const void *a, const void *b)
{
int x = *(const int *)a;
int y = *(const int *)b;
return (x > y) - (x < y); /* no subtraction, no overflow */
}
int main(void)
{
int v[] = { 42, -7, 19, 3, 42, -100, 8 };
size_t n = sizeof v / sizeof v[0];
qsort(v, n, sizeof v[0], cmp_int);
for (size_t i = 0; i < n; i++)
printf("%s%d", i ? " " : "", v[i]);
putchar('\n');
int key = 19;
int *hit = bsearch(&key, v, n, sizeof v[0], cmp_int);
if (hit != NULL)
printf("found %d at index %td\n", *hit, hit - v);
key = 20;
hit = bsearch(&key, v, n, sizeof v[0], cmp_int);
if (hit == NULL)
printf("%d not present\n", key);
return 0;
}
qsort and bsearch know nothing about your data except its element width and the comparator you supply, so all correctness lives in that comparator and in both calls agreeing on the same ordering.
Worked examples
Sorting an array of string pointers
Shows the extra level of dereference needed when the elements are themselves pointers.
<stdio.h>
<stdlib.h>
<string.h>
static int cmp_str(const void *a, const void *b)
{
const char *sa = *(const char *const *)a;
const char *sb = *(const char *const *)b;
return strcmp(sa, sb);
}
int main(void)
{
const char *words[] = { "pear", "fig", "apple", "date" };
size_t n = sizeof words / sizeof words[0];
qsort(words, n, sizeof words[0], cmp_str);
for (size_t i = 0; i < n; i++)
puts(words[i]);
const char *key = "date";
const char **hit = bsearch(&key, words, n, sizeof words[0], cmp_str);
if (hit != NULL)
printf("found %s at index %td\n", *hit, hit - words);
return 0;
}
Example explained
Line 1sizeof words[0] is the width of one const char *, so qsort swaps pointers and never touches the characters they point at.
Line 2Inside cmp_str, a points at an array element whose type is already const char *, so one dereference is required before strcmp sees a string.
Line 3strcmp already returns a negative, zero or positive int, so its result can be returned unchanged with no sign fixup.
Line 4hit - words is a ptrdiff_t index into the sorted array, which is why "date" reports 1 rather than its original position 3.
Looking up a struct by one member
Sorts records by an id field and searches with a key object that only fills that field.
<stdio.h>
<stdlib.h>
struct part { int id; const char *name; };
static int by_id(const void *a, const void *b)
{
const struct part *pa = a;
const struct part *pb = b;
return (pa->id > pb->id) - (pa->id < pb->id);
}
int main(void)
{
struct part inv[] = {
{ 704, "bolt" }, { 120, "nut" }, { 908, "washer" }, { 355, "screw" }
};
size_t n = sizeof inv / sizeof inv[0];
qsort(inv, n, sizeof inv[0], by_id);
for (size_t i = 0; i < n; i++)
printf("%d %s\n", inv[i].id, inv[i].name);
struct part key = { 355, NULL };
const struct part *hit = bsearch(&key, inv, n, sizeof inv[0], by_id);
if (hit != NULL)
printf("%d -> %s\n", hit->id, hit->name);
key.id = 500;
hit = bsearch(&key, inv, n, sizeof inv[0], by_id);
printf("500 %s\n", hit != NULL ? "found" : "absent");
return 0;
}
Example explained
Line 1by_id compares a single member, but qsort still moves whole struct part objects because sizeof inv[0] describes the entire record.
Line 2The key is a full struct part, yet only .id is ever read, so leaving name as NULL costs nothing.
Line 3bsearch hands back a pointer to the stored element, which is how the name comes out even though the key never carried one.
Line 4With key.id set to 500 every comparison misses, bsearch returns NULL, and the ternary prints absent.
Important notes
bsearch is specified to call the comparator with the key pointer as the first argument and an array element as the second, so a partially filled key is legal; qsort makes no such promise, so a comparator shared by both must treat its two sides symmetrically.
Passing sizeof arr inside a function that received the array as a parameter gives the size of a pointer, not of the array or its elements, and corrupts memory rather than merely misordering it.
Common mistakes
For an array of char *, writing strcmp((const char *)a, (const char *)b): the parameters point at the pointer objects, so strcmp reads the bytes of an address instead of a string, giving nonsense order or a segfault. One more dereference is required.
Returning *(const int *)a - *(const int *)b: it works on small test data, then overflows once the array holds something like INT_MIN alongside 1000, the sign comes out backwards, and the array is left partly unsorted with no error reported.
Calling bsearch before qsort, or after sorting with a different comparator: present values come back as NULL. bsearch performs no check, and the standard makes an unsorted array undefined behaviour, so the wrong answer is not even guaranteed to be consistent.
Try it yourself
Change, predict, then run
Start from double t[] = {3.5, 1.25, 9.0, 2.5, 7.75, 0.5}; and write one comparator that sorts it into descending order, then print the sorted array. Use bsearch with that same comparator to look for 2.5 and for 4.0, printing the index for a hit and the word absent for a miss.
Open the C workspaceCheck your understanding
An int array is sorted ascending with cmp_asc, then bsearch is called on that array with cmp_desc, which returns exactly the opposite sign for every pair. The key is a value that really is in the array. What should you expect?
- bsearch can report the value as missing, because it narrows the range in the wrong direction
- bsearch still finds it, since the array is sorted and binary search only needs sorted data
- bsearch finds it but returns a pointer to the mirror-image element on the other side of the array
- The call fails to compile, because bsearch verifies that the comparator matches the sort order
Show answer
bsearch chooses which half to keep purely from the sign the comparator returns, so a reversed comparator steers it away from the key and the search ends at NULL; since the standard makes the ordering the caller's responsibility, the outcome is unreliable rather than neatly reversed. Option 1 is tempting because the data genuinely is sorted, but sortedness only helps when it matches the comparator bsearch is using, so the two calls must agree on a single ordering. Comparators are ordinary function pointers, so there is nothing for the compiler to check.