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