On Tuesday, 15 December 2015 at 00:31:45 UTC, Jakob Ovrum wrote:
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.
Actually, it's two I think - `equalRange` calls both `upperBound`
and `lowerBound` after the main search.
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.
I think there are cases where the difference would be meaningful,
although I agree that most of the time it wouldn't be noticeable.
For sorted arrays you won't find any other standard facility
for doing binary search, but the containers RedBlackTree and
BinaryHeap provide something related.
You could also get the upper bound (SortedRange.upperBound) and
calculate the index from its length. If I'm thinking straight,
this might result in fewer comparisons for some patterns.
OK. Thanks for the advice.
