c - 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.