Personally, I would just expose all accelerated algorithms for sorted
ranges, and make the user call them explicitly e.g. if they know their
range is sorted, make them call binarySearch (or whatever) instead of find.
I have two primary reasons for this:
1. Having the function choose the right algorithm puts an undue burden
on the function writer, which translates into increased uncertainty for
the user of the function, "If I call find(assumeSorted(r)), is it going
to use binary search? What if I call SomeThirdParty.find? Will it know
about assumeSorted?"
2. While we're only discussing assumeSorted now, there are a myriad of
other assumeX wrappers that would be useful:
assumeUnimodal(range) - Allows ternary search for maxElement.
assumeDistinct(range) - uniq doesn't need to do anything.
assumePrime(int) - e.g. getFactors(assumePrime(x)) returns [1, x]
assumeAssociative(binOp) - power can work in O(lg(n)).
* power!(binOp)(a, b) := reduce!(binOp)(replicate(a, b))
Do we provide wrappers for these as well, and make the algorithms check
for all relevant ones?
---
I say no. Provide ternarySearch, powerAssociative etc., and let the user
choose them when he/she knows they are the right algorithm. That way,
function writers can focus on writing specialized functions, and
function users can rest assured that the function they are calling is
performing the algorithm that they expect (with the complexity bounds
that they expect).
