Очевидно, что некоторые считают двоичный поиск алгоритмом «разделяй и властвуй», а некоторые - нет. Я быстро погуглил три ссылки (кажется, все они связаны с научными кругами), которые называют его алгоритмом D & C:
http://www.cs.berkeley.edu/~vazirani/algorithms/chap2.pdf
http://homepages.ius.edu/rwisman/C455/html/notes/Chapter2/DivConq.htm
http://www.csc.liv.ac.uk/~ped/teachadmin/algor/d_and_c.html
Я думаю, что по общему мнению, алгоритм D & C должен иметь по крайней мере первые две фазы из этих трех:
- разделить, то есть решить, как вся проблема разделяется на подзадачи;
- Завоевать, т.е. решить каждую из подзадач независимо;
- [необязательно] объединять, то есть объединять результаты независимых вычислений вместе.
Второй этап - завоевание - должен рекурсивно применять ту же технику для решения подзадачи путем разделения на еще более мелкие подзадачи и т. Д. На практике, однако, часто используется некоторый порог для ограничения рекурсивного подхода, так как для задач небольшого размера другой подход может быть быстрее. Например, реализации быстрой сортировки часто используют, например, пузырьковая сортировка, когда размер части массива для сортировки становится небольшим.
Третья фаза может быть неактивной, и, по моему мнению, она не дисквалифицирует алгоритм как D & C. Типичным примером является рекурсивная декомпозиция for -петля, где все итерации работают исключительно с независимыми элементами данных (то есть без сокращения какой-либо формы). Это может показаться бесполезным на первый взгляд, но на самом деле это очень мощный способ, например, выполнять цикл параллельно и использовать такие платформы, как Cilk и Intel TBB.
Возвращаясь к исходному вопросу: давайте рассмотрим некоторый код, который реализует алгоритм (я использую C ++; извините, если это не тот язык, который вам удобен):
int search( int value, int* a, int begin, int end ) {
// end is one past the last element, i.e. [begin, end) is a half-open interval.
if (begin < end)
{
int m = (begin+end)/2;
if (value==a[m])
return m;
else if (value<a[m])
return search(value, a, begin, m);
else
return search(value, a, m+1, end);
}
else // begin>=end, i.e. no valid array to search
return -1;
}
Здесь разделяющая часть - int m = (begin+end)/2;, а все остальное - часть завоевателя. Алгоритм явно написан в рекурсивной форме D & C, хотя берется только одна из ветвей. Однако его также можно записать в форме цикла:
int search( int value, int* a, int size ) {
int begin=0, end=size;
while( begin<end ) {
int m = (begin+end)/2;
if (value==a[m])
return m;
else if (value<a[m])
end = m;
else
begin = m+1;
}
return -1;
}
Я думаю, что это довольно распространенный способ реализации бинарного поиска с помощью цикла; Я намеренно использовал те же имена переменных, что и в рекурсивном примере, так что общность легче увидеть. Поэтому мы можем сказать, что снова вычисление средней точки является частью деления, а остальная часть тела цикла является частью завоевателя.
Но, конечно, если ваши экзаменаторы думают иначе, может быть трудно убедить их, что это D & C.
Обновление: мне только что пришло в голову, что если бы я разработал общую реализацию алгоритма D & C, основанную на скелете, я бы, конечно, использовал бинарный поиск в качестве одного из тестов на пригодность API, чтобы проверить, является ли API достаточно мощным, а также кратким. Конечно это ничего не доказывает:)