Why can slices.BinarySearchFunc return a confident wrong hit, and how do you catch it?

## The shape of the bug A small CLI answers lookups against a local on-disk index. At startup it loads the index's records into a slice, and a lookup does a binary search by record id. The records were sorted - but by **name**, because an earlier feature printed them in name order, and nobody re-sorted them when the id lookup was added. The binary search still runs. It still returns in about log2(n) steps. It just answers a question about a slice that does not have the ordering it assumed: - most present ids come back as **not found**, at an insertion index that is meaningless; - some ids come back **found at the wrong index**, because the comparison happened to hit an equal key on a path it should never have taken; - which ids fail depends on the data layout, so the failure is data-dependent, not deterministic across releases. No panic, no error return, nothing in a log. The precondition of the algorithm is a promise the caller makes and the library takes on trust. ## Why the library cannot help Checking sortedness costs O(n), which would defeat the entire purpose of an O(log n) search - a linear scan for the element would be no more expensive. So the documentation states the requirement ("the slice must be sorted in increasing order, where increasing is defined by cmp") and stops there. The result on unsorted input is not "an error", it is simply undefined. Note the second half of that sentence, because it is the part that bites: **sorted by which comparison?** A slice can be perfectly sorted and still be the wrong input if the search's comparison orders it differently. Sorted-by-name is not sorted-by-id. It is also not sorted-by-id-case-insensitively, and it is not sorted-by-id if one path compares numerically and another lexically - `"10"` sorts before `"9"` as a string. ## Defence 1: one comparison, two call sites The root cause is two orderings that were allowed to drift apart. Fix it structurally: define one key function or one comparison, and make both the sort and the search go through it. If the sorted index is a type - a struct wrapping the slice, with a `Lookup` method - the ordering has exactly one place to live, and the constructor is the only code allowed to sort. ```go func byID(a, b record) int { return strings.Compare(a.ID, b.ID) } func byIDTarget(r record, id string) int { return strings.Compare(r.ID, id) } ``` Both derive from the same field and the same comparison; a reviewer can see at a glance that they agree. ## Defence 2: assert once, where the index is built The O(n) check is unacceptable per lookup and completely acceptable once, at construction: ```go if !slices.IsSortedFunc(recs, byID) { return nil, fmt.Errorf("record index is not sorted by ID") } ``` That converts a silent wrong answer into a loud startup failure - the trade every on-call engineer wants. For a big index where even one pass is costly, the same check can be compiled out behind a build tag or run only in tests. ## Defence 3: the differential test The strongest guard is a test that computes the same answer two ways and compares. A linear scan is obviously correct, so make it the oracle: ```go for _, want := range recs { got, ok := slices.BinarySearchFunc(recs, want.ID, byIDTarget) if !ok || recs[got].ID != want.ID { t.Fatalf("binary search missed %q", want.ID) } } ``` And crucially, test **absent** keys too - ids that sort before everything, after everything, and in the gaps - asserting that the search reports not-found at the same position a linear scan would compute. A test suite that only looks up keys it just inserted, in a slice of five elements, passes happily on unsorted data, because a five-element search inspects almost everything anyway. Feed it a few thousand records with realistic ids and the differential check catches the ordering mismatch on the first run. ## The context this usually arises in This is the classic failure of an optimisation: someone replaces a linear `slices.Index` with a binary search to make lookups faster **without changing behaviour**. Making it faster is easy; the "without changing behaviour" half is the part that needs evidence, and the evidence is the differential test plus the sortedness assertion. Add both in the same change as the optimisation, not afterwards - and keep the linear implementation around in the test as the oracle, since it is now the only thing that can prove the fast path right.