doc: binary_search does not say what order it uses when feeding inputs to callback

[pnkfelix]

I was quite flummoxed last week because I was getting inconsistent answers out of my calls to binary_search in some code.

I eventually realized that my problem was that I was inverting the order of the inputs when generating the output Ordering in the binary_search callback.

But the really frustrating thing was that the current doc for binary_search does not give you the information you need to actually write the callback properly. It seems one's only options are to experimentally determine the input order, or read the source.

So, let's fix the docs here.

---

Here is some sample code illustrating what I mean in this issue:

#![feature(macro_rules)]

macro_rules! print_it {
    ($e:expr) => {
        { println!("{:s}: {}", stringify!($e), $e); }
    }
}

fn main() {
    // use std::slice::BinarySearchResult;

    let s = [1i, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
    let s = s.as_slice();
    print_it!(s);
    print_it!(s.contains(&3));
    print_it!(s.contains(&1));
    print_it!(s.contains(&4));
    print_it!(s.contains(&55));

    fn search_probe_1<T:Ord>(seek_elem: &T, s: &[T]) -> Option<uint> {
        s.binary_search(|candidate| seek_elem.cmp(candidate)).found()
    }
    fn search_probe_2<T:Ord>(seek_elem: &T, s: &[T]) -> Option<uint> {
        s.binary_search(|candidate| candidate.cmp(seek_elem)).found()
    }

    println!("== seek_elem.cmp(candidate) ==");
    print_it!(search_probe_1(&3, s));
    print_it!(search_probe_1(&1, s));
    print_it!(search_probe_1(&4, s));
    print_it!(search_probe_1(&55, s));

    println!("== candidate.cmp(seek_elem) ==");
    print_it!(search_probe_2(&3, s));
    print_it!(search_probe_2(&1, s));
    print_it!(search_probe_2(&4, s));
    print_it!(search_probe_2(&55, s));
}

which prints:

s: [1, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
s.contains(&3): true
s.contains(&1): true
s.contains(&4): false
s.contains(&55): true
== seek_elem.cmp(candidate) ==
search_probe_1(&3, s): Some(6)
search_probe_1(&1, s): None
search_probe_1(&4, s): None
search_probe_1(&55, s): None
== candidate.cmp(seek_elem) ==
search_probe_2(&3, s): Some(6)
search_probe_2(&1, s): Some(3)
search_probe_2(&4, s): None
search_probe_2(&55, s): Some(12)

This illustrates that "just try it and see" is not actually a good strategy for resolving this ambiguity, because feeding the wrong order can give the right answer, i.e. if you happen to pick the middle element for the first lookup.

[pnkfelix]

(to be fair, the current docs arguably do say the order ... it is just very subtle, in my opinion. Best to add an example)