2011-01-07 8 views
11

Это только я, или нет функции бинарного поиска в Фобосе? У меня есть предварительно отсортированный массив, который я хочу выполнить с помощью собственной функции компаратора, но я не могу найти ничего в std.algorithms или std.containers.Двоичный поиск в D 2.0 (Фобос)?

Спасибо!

ответ

16

Использование SortedRange из std.range:

списаны из 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)); 
+0

Ах, вы должны использовать "assumeSorted" ... не ожидал, что, спасибо! :) – Mehrdad

+6

'find()' (и, следовательно, 'canFind()') на самом деле довольно умный, используя разные алгоритмы, основанные на том, какой ввод вводит его. Для того чтобы бинарный поиск работал, данные должны быть отсортированы, поэтому 'acceptSorted()' делает это так, чтобы он был, а затем 'find()' и 'canFind()' достаточно умны, чтобы знать, что двоичный поиск тогда лучший поиск, и это то, что они делают. –

+3

Это не интуитивно, но если вы просто пытаетесь выполнить двоичный поиск. – Trass3r

 Смежные вопросы

  • Нет связанных вопросов^_^