When slices.BinarySearch reports the target is absent, what does its returned index mean?
answer
- the index means something either way
- not a -1 sentinel
- where it would go, not where it is
- the range includes len(s)
- pairs with an insert to stay sorted
basics
~20 sIt is the insertion point: the position the target would occupy if it were placed in the sorted slice. It ranges from 0 to len(s) inclusive, so it can be one past the last element and must be range-checked before indexing.
solid answer
~50 s`slices.BinarySearch(s, target)` returns `(int, bool)`. The bool says whether the target is actually present; the int is meaningful either way. When the bool is true, the int is the **earliest** position holding the target. When it is false, the int is the position where the target **would** appear in sort order - the insertion point - which lies anywhere in `[0, len(s)]` and equals `len(s)` when the target sorts after everything. That is what makes the not-found result useful rather than an error code: you can splice the new element in at that index and the slice stays sorted, or use it as a lower bound for a range query. Two rules travel with it: the slice must already be sorted ascending, and you must check `i < len(s)` before indexing on the not-found path.
code
go · 7 liness := []string{"ant", "bee", "cow"}
i, ok := slices.BinarySearch(s, "bat")
// i == 1, ok == false: "bat" would sort between "ant" and "bee"
j, ok := slices.BinarySearch(s, "dog")
// j == 3 == len(s), ok == false: indexing s[j] here would panicgo deeper
Be ready to name both return values: a position and a found flag. Remember that the position on a miss is where the value would go, not a -1 sentinel, and that the slice must already be sorted.
Explain the insertion-point semantics and its inclusive upper bound of len(s), why that makes the miss result useful for keeping a slice sorted, and that duplicates yield the earliest matching index.
Show you would defend the precondition in code: where sortedness is established, where it is asserted, and how you avoid the panic on the one input that sorts after every element.
Weigh the data structure itself: a sorted slice with binary search is cheap and cache-friendly for read-mostly data, but every insert is an O(n) shift. Decide when a map or a tree is the honest answer instead.
## The two return values ```go func BinarySearch[S ~[]E, E cmp.Ordered](x S, target E) (int, bool) ``` The `bool` answers "is it there?". The `int` is a **position**, and it is meaningful in both cases - which is the part people miss, because in many other languages a failed search returns a sentinel like `-1` and there is nothing more to learn. - **Found**: the index is the earliest position at which `target` appears. If the slice holds duplicates of the target, you get the first one, not an arbitrary one. - **Not found**: the index is the position at which `target` *would* sit if it were inserted while keeping the slice sorted. ```go s := []string{"ant", "bee", "cow"} i, ok := slices.BinarySearch(s, "bat") // i == 1, ok == false - "bat" sorts after "ant" and before "bee" ``` ## The range of the index The insertion point lives in the closed interval `[0, len(s)]` - note the inclusive upper end. Searching for a value that sorts after every element gives `len(s)`, which is a valid insertion position but **not a valid index**. Any code that does `s[i]` on the not-found path without checking `i < len(s)` will panic on exactly the input that sorts last, and that is a bug that survives a long time because most test data does not exercise it. An empty slice always returns `(0, false)`. ## What the insertion point is for The two-value shape turns one search into two answers, which is why the API is built this way. **Maintaining a sorted slice.** Search, and if the element is absent, insert at the returned index; the slice remains sorted with no re-sort: ```go if i, ok := slices.BinarySearch(names, name); !ok { names = slices.Insert(names, i, name) } ``` That pattern also gives you an idempotent add: found means already present, so there is nothing to do. **Range queries.** The insertion point of the low bound is the index of the first element at or after it, so `s[lo:hi]` with two searches gives you every element in a range - a lower bound and an upper bound over a sorted slice, without a scan. **Ordered bucketing.** Given sorted boundary values, the insertion point of a measurement is the index of the bucket it falls into. That is the same trick histogram code uses. ## The precondition nobody enforces The slice must be sorted in ascending order before you call. `slices.BinarySearch` does not verify that and does not panic when it is violated - it simply halves the wrong way and returns a confident, wrong `(int, bool)` pair. If a slice's sortedness is not obvious from the code that produced it, guard it with `slices.IsSorted` at the point the sorted structure is built, or assert it in a test. ## The Func variant and its argument order ```go func BinarySearchFunc[S ~[]E, E, T any](x S, target T, cmp func(E, T) int) (int, bool) ``` Two details differ from `slices.SortFunc`. First, the comparison receives **an element and the target, in that order** - not two elements - so `cmp(x[i], target)` must be negative when the element sorts before the target. Getting the arguments the wrong way round inverts the search silently. Second, the target has its own type parameter `T`, which need not be the element type: you can search a `[]record` for a `string` id, comparing the id field against the target directly, with no dummy record to search for. The same three-way sign convention applies, and the slice must be sorted in increasing order *as that comparison defines it*. ## Cost The search does about log2(n) comparisons - roughly twenty for a million elements. Against a linear `slices.Index`, that is only worth it when the slice is genuinely sorted and either large or searched repeatedly; for a handful of elements, the linear scan is simpler and often faster, and it carries no sortedness obligation for a future maintainer to break.
- What does slices.BinarySearch return when the sorted slice holds several copies of the target?The index of the earliest one, together with true. That is a documented guarantee of this function rather than a property of binary search in general, and it makes the result deterministic: repeated calls on the same slice give the same index, and the earliest position is also the lower bound of the run of equal values.
- How do the arguments to slices.BinarySearchFunc's comparison differ from those of slices.SortFunc's?`SortFunc`'s comparison takes two elements; `BinarySearchFunc`'s takes an element and the target, in that order, and the target may be a different type from the element. That asymmetry is deliberate - it lets you search a slice of records for a plain string id without constructing a dummy record - but it also means swapping the parameters silently inverts the search.
- What must be true of the slice before either binary search call, and what happens if it is not?It must be sorted ascending - and for the Func variant, sorted by the same comparison you are searching with. Neither function checks. On unsorted input the result is undefined: no panic and no error, just a wrong index and a wrong bool. Guard it with `slices.IsSorted` or `slices.IsSortedFunc` where the sorted structure is built, or assert it in a test.
Asking a librarian for a book that is not held: a useful answer is not "no", it is "it would go on this shelf, between these two spines" - which is exactly where you put it when the copy arrives.
saying these in an interview costs you the question
- Expects -1 on a miss, like an index-of function
- Indexes the slice on the not-found path without checking i < len(s)
- Thinks the second return value is an error
- Assumes a duplicate target yields an arbitrary index
- Calls it on a slice nothing guarantees is sorted