Комментарии 7
Не хочу быть дотошным, но название статьи
Решение задач с использованием алгоритма бинарного поиска
предусматривает описание задач, где используется этот бинарный поиск. Вы-же описали сам бинарный поиск. И добавили от себя
В качестве вывода хочется отметить, что знание модификаций алгоритма бинарного поиска может помочь в решении некоторых зазадач.
Этим не хочу уменьшить значение вашей работы, но зашёл сюда только из-за названия и желания узнать, где и как вы его используете, кроме как сортировки. Потому что сортировка с этим алгоритмом описана уже уйму раз.
Это первое. А второе - сортировать с величиной n только в 30 элементов- это значить не сказать ничто. Различные варианты проходов имеют не только время, но разные времена - в зависимости от входных данных. Например, если массив предварительно отсортирован по возрастанию или убыванию. Всё это отражается на времени. Поэтому я не увидел детального теоретической подхода к описанию алгоритма. И величина n тоже должна играть роль. А в свете современных требований к bigdata и возможность параллельного вычисления.
Спасибо за замечания.
Я хотел показать, как алгоритм с небольшими модификациями может быть использован для решения задач и разобрал одну из них с литкода.
Что касается тестов, то я разобрал только один кейс, когда все элементы одинаковы и соответствуют искомому. В таком случае решение задачи приводило бы к линейному времени.
Я учту ваши замечания и пожелания относительно количества разнообразных задач и тестов)
всё же я тоже зашёл думая увидеть какой-то спектр задач (возможно сразу и не бросающихся в глаза по своему решению с помощью бинарного поиска) пошире чем сортировка и поиск. Как бы понятно что модификация по конкретную задачу это хорошо, но это очевидное решение.
то есть надо сначала массив отсортировать
Извините, но дальше не читал. Задача решается одним проходом по списку. Не нужно никаких сортировок и бинарных поисков
int lessCount = 0;
int equalCount = 0;
for (int num : nums) {
if (num < target) {
++lessCount;
}
else if(num == target) {
++equalCount;
}
}
vector<int> result;
result.reserve(equalCount);
for (int i = 0; i < equalCount; ++i) {
result.push_back(lessCount + i);
}
return result;
Спасибо за то, что поделились решением. Оно довольно изящное и за линейное время. Однако цель статьи была несколько иной - показать применение конкретного алгоритма в разных вариациях.
Сейчас думаю, что стоило упомянуть разные варианты решения для полноты картины. От себя добавлю (напомню), что на leetcode в discuss всегда можно найти много интересных подходов к решению.
За что поставил минус:
Провальный пример. Объяснять бинарный поиск на задаче, которая решается одним проходом, было бы нормально, если явно указать, что задача используется только как повод посмотреть на бинарный поиск. Но автор при этом серьёзно рассуждает об O-нотации и о нехороших решениях за O(N).
"Бенчмарки" с милли- и наносекундной точностью и полное отсутствие статистики. Сколько измерений было сделано? Какова вероятность, что показанная разница в скорости решений просто случайна? Писать и правильно интерпретировать бенчмарки - это целое искусство. Рекомендую прочитать книгу Андрея Акиньшина "Профессиональный бенчмарк".
Сравнение алгоритмов разной асимптотической сложности на только одном и к тому же маленьком размере входных данных. Главное же - характер роста времени при росте размера данных - осталось упущено.
За советы спасибо, за минус, конечно, благодарить не могу. Мы можем долго рассматривать варианты улучшения, но, повторюсь, цель была несколько проще: я наяделся, что материал будет полезен тем, кто еще разбирается в нюансах.
Относительно таблицы с миллисекундами: это результы запуска кода на литкоде. Это указано. Наносекунды: обычные го бенчмарки. Здесь никто не ставил целью досконально разобраться именно в замерах скорости, потому что, как вы верно заметили, это тема искусство, и собственно это может быть темой отдельной статьи. Но показать, что есть изменения в скорости хотя бы в прогонах на литкоде стоило.
Относительно примера выше я уже писал ответ на комментарии. Соглашусь, что возможно он не самый удачный.
Решение задач с использованием алгоритма бинарного поиска