Jakob Ovrum via Digitalmars-d-learn
digitalmars-d-learn at puremagic.com
Mon Dec 14 16:31:45 PST 2015
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.
More information about the Digitalmars-d-learn