Почему двоичный поиск является алгоритмом "разделяй и властвуй"?
На экзамене меня спросили, является ли двоичный поиск алгоритмом "разделяй и властвуй". Мой ответ был "да", потому что вы делите проблему на более мелкие подпроблемы, пока не достигнете результата.
Но экзаменаторы спросили, где в нем часть "побеждай", на что я не смог ответить. Они также не одобрили, что это действительно был алгоритм "разделяй и властвуй".
Но везде, куда бы я ни зашел в Интернете, говорится, что это так, поэтому я хотел бы знать, почему, и где в нем часть "победить"?
1 ответ
Merge Sort и Quick Sort алгоритмы используют эти , делят и завоевывают техника (потому что существует 2 подпроблемы), и Binary Search прибывает под уменьшение, и завоюйте (потому что существует 1 подпроблема).
Поэтому Двоичный поиск на самом деле использует уменьшение, и завоюйте технику а не деление и завоюйте технику.
Источник: https://www.geeksforgeeks.org/decrease-and-conquer /