A generic fast search function is provided through slices as well, called binary_search(). As discussed in Chapter 10, Finding Stuff, a binary search returns the index of an element after closing in on its position by repeatedly choosing a half.
To achieve that, there are two prerequisites that the input slice has to satisfy:
- It's sorted
- The element type implements the Ord trait
binary_search() cannot check whether the collection that's provided is sorted, which means that if an unordered collection returns the expected result, it can only be coincidental. Additionally, if there are multiple elements with the same value, any of those can be the result.
Other than using the implicitly provided comparison function (by implementing Ord), binary_search() also has a more flexible sibling—binary_search_by(), which requires a comparison function to be supplied.
Under the hood, this function is comparable to the naive implementation we created in Chapter 10, Finding...
