Can an array be ordered both ascendant and descendant for bsearch to work?

Question

From this link

Because this function may be optimized to use a non-linear search algorithm (presumably a binary search), the elements that compare less than key using compar should precede those that compare equal, and these should precede those that compare greater. This requirement is fulfilled by any array ordered with the same criteria used by compar (as if sorted with qsort).

• In the quoted text, what does it mean the italic part?
• Also, can I order the array descendant? or only ascendant?
• What else kind of order can the elements inside the array being sorted can it be?

Answer 1

In the quoted text, what does it mean the italic part?

The text “the elements that compare less than key using compar should precede those that compare equal, and these should precede those that compare greater” means that if you have two elements of the array, say a[i] and a[j], and compar reports a[i] is “less than” a[j], then i should be less than j (by their integer values), and, if compar reports a[i] is “greater than” a[j], then i should be greater than j. In other words, the relationship between the positions of the elements in the array matches the relationship between their values as reported by compar.

(Note that these words only tell you about the ordering for elements that compar reports as less than or greater than. It does not impose any constraint on ordering for elements that compar reports as equal.)

Also, can I order the array descendant? or only ascendant?

The compar function defines what the ordering is. You may have some notion in your head that 3 < 4 or “apple” is before “banana”, but compar can be any ordering. For this purpose, “ascending” means progress in the order defined; it does not mean necessarily 3 before 4 or “apple” before “banana”. You could, for example, sort integers according to their low bits first, then their second lowest bits, then their third lowest bits, and so on, instead of by their usual values.

What else kind of order can the elements inside the array being sorted can it be?

Any total ordering can be used. A total ordering gives one relationship between any two elements (<, =, or >) and does not contain any “contradictions” to putting the elements in order. Formally, for any x, y, and z, a total ordering satisfies: x ≤ y and y ≤ x implies x = y, x ≤ y and y ≤ z implies x ≤ z, and either x ≤ y or y ≤ x.

Any relationship that satisfies those requirements can be used.

Answer 2

In the quoted text, what does it mean the italic part?

The array must be ordered as with qsort using the same compar function. Note: All possible qsort results are good for that, regardless the original array order (which may give different results, but still good orders for bsearch).

---

Also, can I order the array descendant? or only ascendant?

Only as with qsort using the same comparing function (AKA: it must be ascending).

---

What else kind of order can the elements inside the array being sorted can it be?

None, but note multiple qsort results are possible with multiple initial orders of the same elements.

Answer 3

This part of the quote

the elements that compare less than key using compar should precede those that compare equal, and these should precede those that compare greater.

means that the array should be ordered such a way that all elements that are "less" than key according to the used comparison function (the function that is specified as an argument of calls of the standard functions qsort and bsearch) must precede the elements that are "equal" to key according to the same comparison function and the last in turn must precede the elements that are "greater" than key according to the comparison function.

When we are speaking about ascending or descending order of elements of an array we mean that there is defined the operator < (not necessary the built-in operator < but some user defined function) for elements of the array such that for ascending order this relation !( a[j] < a[i] ) where i < j is kept for all elements of the array while for descending order the relation is !( a[i] < a[j] )

For the standard functions qsort and bsearch the comparison function that sets an order is declared and defined the following way

int cmp(const void *, const void *)

and shall return an integer less than, equal to, or greater than zero if the first pointed element (or key for bsearcj) is considered, respectively, to be less than, to match, or to be greater than the second pointed array element.

You can use the function qsort for example to partition an array according some criterion.

Here is a demonstrative program that sorts an array at first according to the criterion that each element with an odd value is "less" than each element with an even value and then vice versa.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int cmp1( const void *left, const void *right )
{
    int a = *( const int * )left;
    int b = *( const int * )right;
    
    return b % 2 - a % 2;
}

int cmp2( const void *left, const void *right )
{
    return -cmp1( left, right );
}

int main(void) 
{
    enum { N = 10 };
    int a[N];
    
    srand( ( unsigned int )time( NULL ) );
    
    for ( size_t i = 0; i < N; i++ )
    {
        a[i] = rand() % N;
    }
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );
    
    qsort( a, N, sizeof( int ), cmp1 );
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );

    qsort( a, N, sizeof( int ), cmp2 );
    
    for ( size_t i = 0; i < N; i++ )
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );

    return 0;
}

The program output might look like

4 8 8 9 5 2 9 0 1 2 
9 5 9 1 4 8 8 2 0 2 
4 8 8 2 0 2 9 5 9 1 

You can use the function bsearch with the corresponding comparison function to find an element with a specified key.

In this case this array

9 5 9 1 4 8 8 2 0 2 

is sorted in the ascending order according to the function cmp1 and this array

4 8 8 2 0 2 9 5 9 1 

is sorted in the ascending order according to the function cmo2.

On the other hand, you can consider the first array relative to the second array as it is sorted in the ascending order while the second array is sorted in the descending order according to the comparison function cmp1. And vice versa if to consider sorting of the arrays according to the comparison function cmp2.

But if you are using the function bsearch for the binary search then you should provide an order of the array specifying an appropriate comparison function such a way that

the elements that compare less than key using compar should precede those that compare equal, and these should precede those that compare greater.

That is it is always supposed when you use the function bsearch that the array is sorted in the ascending order according to the comparison function.