Make clarifications for binary_search API

[non-descriptive]

Location

https://doc.rust-lang.org/std/primitive.slice.html#method.binary_search

Summary

Documentation states, that

If the slice is not sorted, the returned result is unspecified and meaningless.

but if we try to use binary search on something like [5,4,3,2,1].binary_search(&5) it will end up with error, though the slice is sorted in descending order.
This either requires to fix docs to something like

If the slice is not sorted in ascending order, the returned result is unspecified and meaningless.

or fix actual binary search algorithm by flipping direction of search in case left and right bounds are flipped.

[okaneco]

You can use binary_search_by to search in a reverse-sorted list.

let seek = 5;
let x = [5, 4, 3, 2, 1].binary_search_by(|probe| seek.cmp(probe));
assert_eq!(x, Ok(0));

---

It seems worth mentioning binary_search_by for searching reverse-sorted slices in the binary_search docs, along with adding a small example in binary_search_by.

There are examples of reversing the comparator order for sorting a slice in reverse order.
https://doc.rust-lang.org/1.78.0/std/primitive.slice.html#examples-85
https://doc.rust-lang.org/1.78.0/std/primitive.slice.html#examples-122

[non-descriptive]

In the end I used search_by version, yes, but doc for regular version was confusing by not mentioning this slight requirement.

[workingjubilee]

If the slice is not sorted in ascending order, the returned result is unspecified and meaningless.

If I specify a newtype that is "sorted" in "descending order" because I took an existing type which usually sorts in the usual order (say, u32) and inverted its comparator (possibly a ReverseSorted<u32>), then the slice is still sorted when I call slice.sort(), and so a valid target of slice::binary_search, but is arguably sorted in "descending order". You can call that "ascending" still, but now the descending order is the ascending order, and so I would suggest that introducing "ascending" and "descending" is needlessly vexing.

The only sort order that matters for this is the comparator in Ord: the first index shall be the least element of the set according to the comparator, and the last index shall be the greatest element of the set according to the comparator. That is what is meant by "sorted", here.

[non-descriptive]

and inverted its comparator

Not sure about that part

use std::cmp::Ordering;

#[derive(Debug, PartialOrd, Eq, PartialEq)]
struct N(u32);

impl Ord for N {
    fn cmp(&self, other: &N) -> Ordering {
        self.0.cmp(&other.0).reverse() // is that inverted comparator
    }
}

fn main() {
    let mut vec = vec!(N(2), N(1), N(3), N(5), N(4)); // randomized order
    vec.sort(); 
    let result = vec.binary_search(&N(5));
    println!("{vec:?} {result:?}"); // output [N(1), N(2), N(3), N(4), N(5)] Err(0)
}

Is that what you meant? Sorted in ascending order for a human, but binary search yields error, because of Ord reversed.
Regardless, methinks it's worth mention at least what sorted means in context of binary search. At least mention it respects type's Ord.

[workingjubilee]

Oh, I meant

use std::cmp::Ordering;

#[derive(Debug, Eq, PartialEq)]
struct N(u32);

impl PartialOrd for N {
    fn partial_cmp(&self, other: &N) -> Option<Ordering> {
        Some(self.cmp(&other))
    }
}

impl Ord for N {
    fn cmp(&self, other: &N) -> Ordering {
        self.0.cmp(&other.0).reverse()
    }
}

fn main() {
    let mut vec = vec!(N(2), N(1), N(3), N(5), N(4)); // randomized order
    vec.sort(); 
    let result = vec.binary_search(&N(5));
    println!("{vec:?} {result:?}"); // output [N(1), N(2), N(3), N(4), N(5)] Err(0)
}

The integers are sorted in descending order if you look at the values but the comparator sees them as being in "ascending order", so the sense used for "sorted" in the docs for slice::binary_search.