This is a wild guess, but maybe the Search function could be a bit better than expected if it was a bit smarter about allocation size than the regular version y

This is a wild guess, but maybe the Search function could be a bit better than expected if it was a bit smarter about allocation size than the regular version you posted. From what I understand, the initial capacity of slices is 0, which would mean that you get a few reallocations with the "naive" version. Search, on the other hand, could allocate a slice with a capacity that's a half of xs, so you only need one reallocation at worst. This, mixed with the "Partition" function proposed by sibling comments (which would only iterate once) could lead to code that's faster than the regular approach, while also being shorter to write. On the other hand, it's not as free as it seems, as now developers have to know the Partition function, and how it works. It may also have pitfalls that I haven't considered. As always, it's hard to find the perfect sweet spot between how much stuff developers should know and how much stuff should be explicit in the code all the time.