один вопрос о двоичном поиске

Вероятно, можно предположить, что комментарий был несерьезным.

Я не могу вообразить никого утверждающего, что модуляризация и абстракция - плохая практика и на самом деле значение его.

Когда каждая функция (и вспомогательные функции) находится в собственном модуле?

Для разделения массива пополам требуется только ОДИН оператор сравнения.

Разделение на три потребует более одного (иногда одного, иногда двух) сравнения.

Википедия должна дать вам немного больше объяснений, включая математику за ней

Двоичный формат позволяет легко сравнивать <= или> = или <или> (не могу вспомнить, что обычно используется). Он аккуратно разделяет набор, и его легко придумать. Как бы вы разделили произвольные наборы данных на разные части? Как бы вы решили, в какую часть что-то вставить? Двоичный поиск требует O (log n) поисков. Добавление дополнительных компонентов изменит это значение на что-то близкое к O (m * log n), где m - количество частей, на которые вы делите.

Джейкоб

Это значительно упрощает логику:

if(cond)
Go Left
else
Go Right

По сравнению с оператором switch.

Есть много веских общих причин следовать минимализму, когда речь идет о разрешениях, но в контексте webhost LAMP немногие, которые легко приходят на ум

• На общей хостинговой платформе, другие пользователи, делящиеся вашим хостом, теперь могут читать и писать в ваши сценарии.
• На выделенном хосте незаконные процессы могут считывать/записывать и случайно удалять файлы. Допустим, существует пользовательский процесс регистрации, выполняемый в фоновом режиме как пользователь, у которого нет ошибки, которая приводит к попытке rm -rf/. Теперь, как правило, это будет безобидным, потому что вряд ли будет какой-либо файл, который никто не должен иметь разрешения на запись, но этот незаконный процесс теперь возьмет ваши файлы с собой.
• Чтобы испортить ваш веб-сайт, кто-то должен получить доступ только как любой пользователь, даже сказать никто или какой-то такой фиктивный аккаунт. Как правило, злоумышленник должен сделать еще одну атаку на уровне пользователя, чтобы добраться до места, где он может нанести некоторый ущерб. Это реальная угроза. Некоторые некритические службы могут работать под фиктивными учетными записями и содержать уязвимость.

Кроме того, вы можете использовать VS и для разработки Android, потому что в конечном итоге IDE - это не что иное, как модный текстовый редактор с ярлыками на инструментах командной строки, так что большинство популярных IDE можно использовать.

Однако, если вы хотите разработать полностью собственные без ограничений, у вас будут все виды проблем, например, связанные с нечувствительностью файловой системы к кейсу и отсутствующими библиотеками на платформе Windows.

Если вы попытаетесь создать мобильные приложения Windows на платформе Linux, у вас будут более серьезные проблемы, чем в другом случае, но все же имеет смысл использовать Linux с Eclipse для ОС Android.

, поскольку двоичный поиск основан на разделении по простой операции, деление, которое всегда дает один ответ, что означает одну точку отсечения, так что если вы можете придумать вопрос, который имеет два ответа, вы можете иметь две точки отсечения и так далее

На самом деле в системах баз данных обычно используются N-сторонние деревья поиска, а не двоичные деревья. Хотя количество сравнений может быть больше O (log2 n), количество операций чтения существенно меньше. Ознакомьтесь с B-деревьями и их вариантами.

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

Таким образом, двоичный поиск проще, потому что он предъявляет меньше требований к сравнению.

Причина в том, что вы на самом деле ничего от этого не получаете: поиск по-прежнему O (log п) , только с другой базой.

Потому что двоичный поиск дает наименьшее количество сравнений и поисков. Для простой интуиции рассмотрите возможность деления на 4 части каждый раз.

[         |         |    .    |         ]
          v1        v2        v3

Теперь вы выполнили 3 поиска и должны сравнить значение, которое вы ищете, в худшем случае, со всеми тремя значениями. Сравните это с двумя итерациями двоичного поиска:

[                   |    .              ]
                    v1
[                   |    .    |         ]
                    v1        v2

Теперь вы сузили диапазон поиска на ту же величину, но выполнили только 2 поиска и 2 сравнения.

Никто не упомянул, что операторы сравнения, реализованные во всех компьютерах, сравнивают только две вещи одновременно - если бы компьютер мог сравнивать три объекта одновременно, это имело бы смысл.

В нынешнем виде для сравнения трех значений требуется (по крайней мере) две операции.

Двоичный поиск использует 1 сравнение, чтобы сократить n до n / 2. троичный поиск использует 2 сравнения, чтобы сократить n до n / 3.

Таким образом, сложность первого варианта равна 1. log2 n, второго - 2. log3 n или log3 n ^ 2

log2 n всегда лучше, чем log3 n ^ 2.

Чтобы увидеть это,

возводит оба значения в степень 3, 3 ^ log2 n vs n ^ 2

=> 3 ^ (log2 3. Log3 n) vs n ^ 2

=> n ^ (log2 3) vs n ^ 2

, поэтому двоичный поиск быстрее любого m-арного поиска. вы сравниваете log2 m vs (m-1).

Кстати, поиск с интерполяцией асимптотически быстрее, чем двоичный поиск с loglogN. Но не стоит беспокоиться, если только ваши данные не огромны. [поэтому приведенный выше комментарий о наилучшем возможном поиске теоретически неверен!]