11

Is it just me, or is there no binary search function in Phobos? I have a pre-sorted array that I want to search with my own comparator function, but I can't find anything in std.algorithms or std.containers.

Thanks!

user541686
  • 205,094
  • 128
  • 528
  • 886

1 Answers1

16

Use SortedRange from std.range:

Cribbed from http://www.digitalmars.com/d/2.0/phobos/std_range.html#SortedRange:

auto a = [ 1, 2, 3, 42, 52, 64 ];
auto r = assumeSorted(a);
assert(r.canFind(3));
assert(!r.canFind(32));
Matt Curtis
  • 23,168
  • 8
  • 60
  • 63
  • Ah, you have to use "assumeSorted"... didn't expect that, thanks! :) – user541686 Jan 07 '11 at 04:36
  • 6
    `find()` (and thus `canFind()`) is actually pretty smart, using different algorithms based on what type input its given. In order for binary search to work, the data has to be sorted, so `assumeSorted()` makes it so that it is, and then `find()` and `canFind()` are smart enough to know that binary search is the best search then, and that's what they do. – Jonathan M Davis Jan 07 '11 at 11:33
  • 3
    It's not intuitive at all though if you are simply trying to do a binary search. – Trass3r May 11 '12 at 18:42
  • 1
    It's late and I'm tired, but I suspect the design is good, I mean, it seems cool to bring strong typing to the concept of sortedness, and to separate 'what you want to do' from 'how it gets done'. D just needs a solid body of questions and answers like this one so that people can learn these things quickly with Google. – Qwertie Jul 07 '12 at 06:55