0


Изучаю алгоритм бинарной сортировки, в книге (Грокаем Алгоритмы), в других описаниях вскользь говорится, что мол mid = (low + high) / 2 (с округлением в меньшую сторону). Я не понимаю, почему делают именно floor округление.
Вопрос: можно ли использовать ceil округление? Если да, то в каких случаях выбирать ceil, а в каких floor? Прочитал, что есть две разновидности этого алгоритма для нахождения первого и последнего вхождения числа в массив, возможно в этих случаях это принципиально(если не сложно можете написать код того и другого)?
В прямом смысле, первый алгоритм после линейного который начал изучать, поэтому, пожалуйста, аккуратнее с терминами. Спасибо всем кто ответит, ссылки на статьи, примеры, разъяснения - все изучу :)

3
  • Это всё исторически сложилось. floor быстрее, реализуется с помощью битового сдвига. Можно даже делить (1/3 : 2/3) всё равно будет логарифмическая сложность.
    – AlexGlebe
    Commented 7 мар. 2020 в 12:28
  • @AlexGlebe я был очень за, что это просто так сложилось исторически, но цитирую: "Существуют две модификации этого алгоритма для поиска первого и последнего вхождения. Все зависит от того, как выбирается средний элемент: округлением в меньшую или большую сторону. В первом случае средний элемент относится к левой части массива, а во втором - к правой." - и вот тут я как взял, так и ничего не понял в два раза больше) Т.к. после этого отрывка не было примеров кода. Commented 7 мар. 2020 в 12:35
  • Поиску элемента в отсортированном массиве может быть нужно крайние одинаковые значения, а для сортировки - нет. Всё зависит от вашей задачи. Можете искать оба края - это ваше право.
    – AlexGlebe
    Commented 7 мар. 2020 в 12:48

1 ответ 1

2

Неважно в какую сторону округлять. Главное чтобы сохранялся инвариант f(l) != f(r)

Ваш ответ

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

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.