Binary search

[Jakob Ovrum via Digitalmars-d-learn]

On Tuesday, 15 December 2015 at 00:22:37 UTC, tsbockman wrote:
> I also found `SortedRange.equalRange`, but that sounds like it 
> has an unreasonable amount of (admittedly O(1)) overhead for 
> the (extremely common) case in which I am looking for only a 
> single element, not a range.

If your array doesn't contain duplicates, the overhead is just 
one extra comparison. For cheap comparisons, this overhead will 
be completely dwarfed by the actual search (assuming your array 
is big enough to justify binary search over linear search). If 
your array contains duplicates but you are only interested in 
getting any one of them, or your comparison is non-trivial, then 
I agree this could potentially be a problem.

For sorted arrays you won't find any other standard facility for 
doing binary search, but the containers RedBlackTree and 
BinaryHeap provide something related.