Почему бинарный поиск является алгоритмом «разделяй и властвуй»?

Question

Меня спросили, является ли бинарный поиск алгоритмом «разделяй и властвуй» на экзамене.Мой ответ был положительным, потому что вы разделили проблему на более мелкие подзадачи, пока не достигли своего результата.

Но экзаменаторы спросили, где в этом была роль победителя, но я не смог ответить.Они также не одобряли тот факт, что на самом деле это был алгоритм «разделяй и властвуй».

Но везде, где я хожу в Интернете, он говорит, что это так, поэтому я хотел бы знать, почему и где его часть покорения?

Answer 1

Алгоритмы двоичного поиска и троичного поиска основаны на технике уменьшения и завоевания.Поскольку вы не делите проблему, вы фактически уменьшаете проблему, деля на 2 (3 в троичном поиске).

Алгоритмы сортировки слиянием и быстрой сортировки могут быть приведены в качестве примеров техники разделения и завоевания.Вы делите задачу на две подзадачи и снова используете алгоритм для этих подзадач, чтобы отсортировать массив.Но вы отбрасываете половину массива в бинарном поиске.Это означает, что вы УМЕНЬШИТЕ размер массива, а не делите.

Answer 2

Я думаю, что это Уменьшение и Победа.

Вот цитата из Википедии.

"Вместо имени было предложено уменьшить и победить класс одной подзадачи "

http://en.wikipedia.org/wiki/Divide_and_conquer_algorithms#Decrease_and_conquer

Насколько я понимаю, "Завоевать" часть находится в конце, когда вы найдете целевой элемент двоичного поиска. Часть «Уменьшение» уменьшает пространство поиска.

Answer 3

Дихотомия в информатике означает выбор между двумя противоположными вариантами, между двумя различными альтернативами.Дихотомия - это любое разбиение целого на ровно две непересекающиеся части, то есть это процедура, в которой целое делится на две части.Это разделение целого (или набора) на две части (подмножества): 1. Совместно исчерпывающий: все должно принадлежать одной или другой части, и 2. Взаимоисключающий: ничто не может принадлежать одновременно обеим частям.

Делите и властвуйте, рекурсивно разбивая проблему на две или более подзадачи одного и того же типа, пока они не станут достаточно простыми для непосредственного решения.

Таким образом, двоичный поиск делит пополамколичество элементов для проверки на каждой итерации и определяет, есть ли у него шанс найти «ключевой» элемент в этой половине или перейти к другой половине, если он может определить отсутствие ключей.Поскольку алгоритм дихотомичен по своей природе, бинарный поиск будет полагать, что «ключ» должен находиться в одной части, пока не достигнет условия выхода, при котором возвращается, что ключ отсутствует.

Answer 4

Бинарный поиск - это алгоритм «разделяй и властвуй»:

1) В алгоритмах «Разделяй и властвуй» мы пытаемся решить проблему, решая меньшую подзадачу (Разделить часть), и используем это решение для построения решения для нашей более крупной проблемы (Завоевать).

2) Здесь наша задача - найти элемент в отсортированном массиве. Мы можем решить эту проблему, решив аналогичную подзадачу. (Здесь мы создаем подзадачи на основе решения, что искомый элемент меньше или больше среднего элемента). Таким образом, когда мы знаем, что элемент не может существовать наверняка в одной половине, мы решаем аналогичную подзадачу в другой половине.

3) Таким образом, мы рекурсивно.

4) Здесь часть conquer просто возвращает значение, возвращаемое подзадачей, на вершину рекурсивного дерева

Answer 5

Неформальное определение более или менее: разделите проблему на маленькие проблемы.Тогда решите их и соедините их (победите).Решение на самом деле решает, куда идти дальше (влево, вправо, найден элемент).

Здесь цитата из wikipedia :

Название «разделяй иconquer "иногда применяется также к алгоритмам, которые сводят каждую проблему только к одной подзадаче, например к алгоритму двоичного поиска для поиска записи в отсортированном списке.

Это означает, что это НЕ [обновление: неверное прочтение этой фразы :)] только одна часть разделяй и властвуй.

Обновление: Эта статья прояснила ситуациюдля меня.Я был сбит с толку, так как определение говорит, что вы должны решить каждую подзадачу.Но вы решили подзадачу, если знаете, что вам не нужно продолжать поиск ..