C sorting and searching use void pointers, an element count, a byte stride and a comparison callback. This makes them usable across a C ABI, but removes the type guidance of C++ algorithms. Reconstruct the exact argument types at the boundary.
A comparator promises an order
qsort calls the record comparator with pointers to two real elements. Return a negative value, zero or a positive value for their ordering. Subtracting full-range signed keys can overflow, so compare relations instead. The callback must be consistent and must not mutate the objects it compares.
The build orders records by key and then serial. That explicit tie-breaker is different from asking qsort to be stable: qsort promises neither stability nor a specific quicksort implementation. Equal complete records may be reordered. There is no portable fixed-complexity grading assumption in this exercise.
Follow one complete example
Run this program, then change one boundary while keeping the API preconditions valid. Predict its output before pressing Run.
#include <cstdio>
#include <cstdlib>
#include <limits>
int compare(const void* a,const void* b) {
int x=*static_cast<const int*>(a),y=*static_cast<const int*>(b);
return (x>y)-(x<y);
}
int main() {
int a[]={std::numeric_limits<int>::max(),0,std::numeric_limits<int>::min()};
std::qsort(a,3,sizeof a[0],compare);
int key=0;auto found=static_cast<const int*>(std::bsearch(&key,a,3,sizeof a[0],compare));
std::printf("%d %d\n",a[0]<0,found?*found:99);
}Keep element counts and byte strides separate
Pass records.size() as the number of elements and sizeof(c_record) as each element size. sizeof a pointer is not the stride of the pointed-to array. The backing storage must actually contain that many elements. Guard an empty span in this adapter instead of depending on a null base-pointer case.
In C++, use qsort only where its representation-moving contract is appropriate, such as this trivially copyable record. std::string and other nontrivial resource-owning objects need typed algorithms and their move/copy operations. Prefer std::sort or ranges algorithms for ordinary C++ containers; learn qsort for C interfaces and legacy code rather than as a generic C++ performance shortcut.
A search key can have a different type
bsearch passes the key pointer first and an element pointer second. Here the first points to int while the second points to c_record. Reusing a record-to-record callback by blindly casting the key is a type error even if one field seems to line up by accident.
Search the range only after it is ordered consistently by key. Check the returned pointer for nullptr. The pointer borrows the original storage and may identify any matching duplicate; first-match behavior belongs to a different API such as lower_bound. Test comparator extremes directly, then use randomized sorting against a typed reference and membership checks that do not assume a duplicate index.
Read the return value
Predict this smaller case. The check item later changes the values, so explain the rule as well as the output.
#include <cstdio>
#include <cstdlib>
int cmp(const void* a,const void* b){int x=*static_cast<const int*>(a),y=*static_cast<const int*>(b);return (x>y)-(x<y);}
int main(){int a[]={3,1,2},key=2;std::qsort(a,3,sizeof(int),cmp);auto p=static_cast<const int*>(std::bsearch(&key,a,3,sizeof(int),cmp));std::printf("%d%d%d %d\n",a[0],a[1],a[2],*p);}Complete the faded example
State the missing precondition or result check before filling the code. The fill exercise supplies the rest of the implementation.
int compare_record_key(const void* key, const void* element) {
// Fill: cast each pointer to its actual, different type.
// Fill: return an overflow-safe comparison sign.
}Check your model
Why may a test check the matching key but not insist that bsearch returned the first record with that key?
Practice the boundary
Implement the supplied trivially copyable c_record interface using qsort and bsearch.
compare_records(left,right) compares records by ascending key, then ascending serial. compare_record_key(key,element) compares a pointed-to int key with a pointed-to c_record. Comparators return a negative value, zero or a positive value; they must work across the full int range without subtraction overflow or mutation.
sort_records(span<c_record>) sorts in place in that order. find_record(span<const c_record>,int) borrows an already-sorted range and returns a pointer to any record with that key, or nullptr if absent. Returned pointers belong to the caller's storage; duplicates do not promise the first match. Empty ranges are supported without calling a C function on a null base pointer. Comparators do not throw. Use the actual element byte size, not the pointer size. This task makes no qsort algorithm or stability promise.
Read → six checks → two bug hunts → fill → build. A successful graded submission is evidence; reading or watching alone does not grant mastery. Review cards reinforce API choices separately.
Watch and verify
The Watch & read panel links a free lecture for the relevant background and primary API references. The lecture notes say which parts are background; the tested contract here supplies the exact wrapper policy.
C standard-library course · C library review cards · Unix/Linux systems