Opportunistic worst-case complexity upgrade? aka binary search with `find`

[Jakob Ovrum via Digitalmars-d]

On Thursday, 24 July 2014 at 21:08:58 UTC, Jonathan M Davis wrote:
> On Thursday, 24 July 2014 at 01:26:48 UTC, Jakob Ovrum wrote:
>> On Thursday, 24 July 2014 at 01:21:44 UTC, Jakob Ovrum wrote:
>>> -snip-
>>
>> Another point is that the range types of the two currently 
>> available sorted containers - RedBlackTree and BinaryHeap - 
>> are *not* instances of SortedRange. If algorithms working on 
>> sorted ranges become a thing, it seems like they should be.
>
> Maybe a better approach would be do just have sorted range 
> types define find themselves? UFCS would then make it so that 
> the best search function for that type would be used (e.g. I 
> don't think that binary search is the best method to use a 
> red-black tree).

Right, the two tree structures can't be searched properly using a 
generic binary search algorithm.

I don't think having containers define `find` as a member is 
really feasible. `find` is a highly generic function with a 
multitude of forms, and to be interchangeable, every container 
would have to support all these forms. That sounds extremely 
impractical.

> However, regardless of that, it could be useful to know whether 
> a range is sorted or not in general, and we may want to change 
> how we do that so that there's an enum which indicates it 
> rather than simply wrapping it in SortedRange (e.g. we know 
> that RedBlackTree's range type is sorted, but I doubt that we 
> want to always be wrapping it in a SortedRange to show that).
>
> - Jonathan M Davis

The container could simply make its Range type an alias to 
SortedRange!(RangeImpl, pred). It wouldn't cost anything. But, of 
course, as you pointed out, it's not possible for the tree 
structures, at least not without changing something in 
SortedRange.

Maybe SortedRange's search functions should defer to the 
underlying range if the underlying range supports logarithmic 
search, such as by defining `lowerBound` et al. as members of the 
range type. This would cause some duplication of course, as 
currently, `lowerBound` et al. are container primitives. However, 
wouldn't it be the right place for them?

Currently, using `SortedRange`, we can do binary search on a 
*subset* of the original range, as its search functions in turn 
return sorted ranges:

---
auto data = [1, 2, 3, 4, 5].assumeSorted();

auto lower = data.lowerBound(5);
auto target = lower.upperBound(1); // Narrower search area!

assert(target.equal([2, 3, 4]));
---

In the current container model, where they are primitives of the 
container and not the container's range, this is not possible.