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