Binary search

[tsbockman via Digitalmars-d-learn]

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.