Students are set exercises. The purpose of an exercise
is to get stronger. Sometimes binary search is offered.
The idea is to discover the loop invariant. Eventually
the student learns to write for the edge and corner cases
_first_. Thus a purpose of the exercises is realized.
I am surprised at how many people here admit to not
knowing how to write a binary search.
The idea is that in writing a binary search in place
one avoids having to write an interface to a library
routine. I embed bits of code in the search routine
itself, rather than interpreting the library routine
results and then doing what I need.
I cannot see myself ever calling bsearch(3). I will
call qsort(3). Note the existence of qsort_r.
Sometimes I'll write an insertion sort with binary
search. Sometimes I'll write a heapsort. This stuff
is not hard.
In this day and age with more and more glue coders, knowing how to
write a binary search is not required anymore. Beneficial yes, but
not required for many programmers. However, having someone on the
team that can do algorithm work when needed is still vital.
And I agree that bsearch is not hard with some study, but you've then
doomed yourself to cut-and-paste search algorithms for every little
quirk of data type or search semantic. There are methods to abstract
bsearch within an array container that make it quite useful, and the
value of providing a canned search algorithm to less skilled coders
cannot be understated.
(crosses fingers that my bsearch is "right")
\code snippet
/*!
* \brief Searches a \c c_array for an object that matches the given
* value using a binary search algorithm.
* \param array A \c c_array.
* \param object The object to find.
* \param cmp_fn The function to call for each object comparison. It
* should return 0 when the objects match.
* \param type The object type.
* \return The address of the object in the array, or \c NULL if the
* object is not found in the array.
*
* The \c c_array_bsearch function requires the array to be sorted
* prior using this to search objects in the array. This sorting
* can be done during insertion using \c c_array_insert_sorted, or
* after all the objects have been inserted into the array using
* \c c_array_sort. If the \c c_array is not sorted, there is the
* possibility for false negatives.
*
* The binary search algorithm is preferred for large arrays of
* objects as the performance of the algorithm is O(log n) rather
* than O(n) for the \c c_array_search and \c c_array_rsearch
* functions. Keep in mind that if duplicate objects are in the
* array, the \c c_array_bsearch algorithm may point to any one of
* them rather than the first or last instance of the object.
*/
#define c_array_bsearch( array, object, cmp_fn, type ) ( (type*)
(gc_array_bsearch( (array), (object), (cmp_fn), sizeof(type) )) )
void* gc_array_bsearch( struct c_array* array,
const void* object,
c_compare_function cmp_fn,
size_t type_sz )
{
void* found = NULL;
ssize_t l, h, m;
void* m_p;
int cmp;
if ( array && cmp_fn )
{
C_ASSERT( array->element_size == type_sz );
if ( array->size )
{
/*
* l - low boundary of region to search
* h - high boundary of region to search
* m - median of region to search (if array is sorted)
* m_p - pointer to the corresponding median object in the
array.
*/
l = 0;
h = array->size - 1;
while ( l <= h )
{
/*
* The following statement gets the midpoint of the range,
* by obtaining the average using a slightly obtuse method.
*
* The normal method to get the midpoint of a range is to
* sum the low and high boundary and divide by 2.
*
* (high + low) / 2
*
* The problem is that this limits the maximum value of the
* mid-point to SSIZE_MAX / 2 without encountering overflow.
*
* low + ((high - low) / 2) or
*
* 2/2 low + 1/2 high - 1/2 low == (high + low) / 2
*
* This still evaluates to the expression '(high + low) / 2',
* but avoids the overflow issue from 'high + low'.
*/
m = l + ((h - l) / 2);
m_p = gc_array_at( array, m );
cmp = cmp_fn( m_p, object );
if ( cmp < 0 ) {
l = m + 1;
}
else if ( cmp > 0 ) {
h = m - 1;
}
else
{
found = m_p;
break;
}
}
}
}
return found;
}
/*!
* \brief Inserts a new object into the array using the comparison
* function.
* \param array A \c c_array.
* \param object The object.
* \param cmp_fn The function to compare objects in the array.
* \param type The object type.
*/
#define c_array_insert_bsorted( array, object, cmp_fn, type )
(gc_array_insert_bsorted( (array), (object), (cmp_fn), sizeof(type) ))
void gc_array_insert_bsorted( struct c_array* array,
void* object,
c_compare_function cmp_fn,
size_t type_sz )
{
size_t index = 0;
ssize_t l, h, m;
void* m_p;
int cmp;
if ( array )
{
C_ASSERT( array->element_size == type_sz );
if ( cmp_fn )
{
if ( array->size )
{
/*
* l - low boundary of region to search
* h - high boundary of region to search
* m - median of region to search (if array is sorted)
* m_p - pointer to the corresponding median pointer in the
array.
*/
l = 0;
m = 0;
h = array->size - 1;
cmp = 0;
while ( l <= h )
{
m = l + ((h - l) / 2);
m_p = gc_array_at( array, m );
cmp = cmp_fn( m_p, object );
if ( cmp < 0 ) {
l = m + 1;
}
else if ( cmp > 0 ) {
h = m - 1;
}
else {
break;
}
}
/*
* At the end of the loop, the value of cmp will determine
which
* side of the object referenced by 'm_p' to insert the
object.
* If the object at 'm_p' is equal or greater than the object
* to be inserted, the insert should place the object before
the
* location 'm'. If it is less, the object should be placed
* after location 'm'.
*/
index = m;
if ( cmp < 0 ) {
++index;
}
}
}
gc_array_insert( array, index, object, array->element_size );
}
}
\endcode
By creating appropriate comparison functions, one can sort and search
based on different fields of a structure quite easily. In my opinion,
writing a valid comparison function is much easier than man-coding
each search as you need them, especially if your struct has several
members to sort and search on. You admit to using qsort, but don't
see the benefit of bsearch? Doesn't seem logical to me.
The real question is whether one should in general trust the standard
C library bsearch implementation over yet another custom coded binary
search that some other programmer designed? If you're creating a
binary search with sprinkles, like one that modifies the container
while searching, that is something different.
Best regards,
John D.
