Недостаток доступа к среднему элементу с помощью двоичного поиска

Question

• 1000 средний элемент в списке. Это означает, что список должен храниться в линейном массиве определенного типа. Затем в книге говорится:

К сожалению, вставка элемента в массив требует перемещения элементов вниз по списку, а удаление элемента из массива требует перемещения элемента вверх по списку.

Как это недостаток? Разве мы не сможем получить доступ к среднему элементу, разделив длину массива на 2?

Answer 1

В случае, когда массив не будет изменен, стоимость вставки и удаления не имеет значения.

Однако, если массив должен использоваться для поддержания отсортированного набора нефиксированных элементов, тогда актуальны затраты на вставку и удаление. В этом случае бинарный поиск может использоваться для поиска элементов (возможно, для удаления) и / или поиска места для вставки новых элементов. Недостатком является то, что вставка и удаление требуют перемещения других элементов. Модуль

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

В некоторых случаях двоичное дерево поиска может быть предпочтительной альтернативой отсортированному массиву для поддержания отсортированного набора нефиксированных элементов.

Answer 2

Кажется, что автор сравнивает структуры, подобные массиву, и связанный список

Первый (массив, Python и Java список, вектор C ++) обеспечивает быстрый и простой доступ к любой элемент по индексу, но добавление, вставка или удаление может вызвать перераспределение памяти.

Для второго мы не можем напрямую адресовать i-й элемент, нам нужно пройти по списку с самого начала, но когда у нас есть элемент - мы можно быстро вставить или удалить.