• tsbockman (8/8) Dec 14 2015 Is there no way to do a simple binary search of a sorted array
• Jakob Ovrum (11/15) Dec 14 2015 If your array doesn't contain duplicates, the overhead is just
• Jakob Ovrum (4/7) Dec 14 2015 You could also get the upper bound (SortedRange.upperBound) and
• tsbockman (6/25) Dec 14 2015 Actually, it's two I think - `equalRange` calls both `upperBound`

tsbockman <thomas.bockman gmail.com> writes:

Is there no way to do a simple binary search of a sorted array 
using Phobos?

I found `SortedRange.contains`, but that just returns true/false. 
I want the index of the element, or the element itself.

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.

Jakob Ovrum <jakobovrum gmail.com> writes:

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.

Jakob Ovrum <jakobovrum gmail.com> writes:

On Tuesday, 15 December 2015 at 00:31:45 UTC, Jakob Ovrum wrote:
 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.

tsbockman <thomas.bockman gmail.com> writes:

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.