Binary Search-访问中间元素的缺点
Binary Search-accessing the middle element drawback
我正在学习 Seymour Lipschutz 的数据结构课程书，我遇到了一个我不完全理解的点..
Binary Search Algorithm assumes that one has direct access to middle element in the list. This means that the list must be stored in some typeof linear array.
我读了这篇文章并认识到在 Python 中您可以随时访问中间元素。然后这本书接着说：
Unfortunately, inserting an element in an array requires elements to be moved down the list, and deleting an element from an array requires element to be moved up the list.
这是怎么个缺点？
数组长度除以2不就可以访问到中间的元素了吗？
作者似乎比较了 array-like 结构和 linked list
第一个（数组，Python 和 Java 列表，C++ 向量）允许通过索引快速简单地访问任何元素，但是追加、插入或删除可能会导致内存重新分配。
第二种我们不能直接寻址i-th元素，需要从头开始遍历list，但是当我们有元素时-我们可以快速插入或删除。
在数组不会被修改的情况下，插入和删除的代价是不相关的。
但是，如果要使用数组来维护一组已排序的 non-fixed 项，则插入和删除成本是相关的。在这种情况下，可以使用二进制搜索来查找项目（可能用于删除） and/or 找到应该插入新项目的位置。缺点是插入和删除需要移动其他元素。
Python 的 bisect 模块提供二进制搜索功能，可用于定位插入点以维护排序顺序。提到的缺点适用。
在某些情况下，binary search tree 可能是排序数组的更好替代方案，用于维护 non-fixed 项的排序集。
我正在学习 Seymour Lipschutz 的数据结构课程书，我遇到了一个我不完全理解的点..
Binary Search Algorithm assumes that one has direct access to middle element in the list. This means that the list must be stored in some typeof linear array.
我读了这篇文章并认识到在 Python 中您可以随时访问中间元素。然后这本书接着说：
Unfortunately, inserting an element in an array requires elements to be moved down the list, and deleting an element from an array requires element to be moved up the list.
这是怎么个缺点？ 数组长度除以2不就可以访问到中间的元素了吗？
作者似乎比较了 array-like 结构和 linked list
第一个（数组，Python 和 Java 列表，C++ 向量）允许通过索引快速简单地访问任何元素，但是追加、插入或删除可能会导致内存重新分配。
第二种我们不能直接寻址i-th元素，需要从头开始遍历list，但是当我们有元素时-我们可以快速插入或删除。
在数组不会被修改的情况下，插入和删除的代价是不相关的。
但是，如果要使用数组来维护一组已排序的 non-fixed 项，则插入和删除成本是相关的。在这种情况下，可以使用二进制搜索来查找项目（可能用于删除） and/or 找到应该插入新项目的位置。缺点是插入和删除需要移动其他元素。
Python 的 bisect 模块提供二进制搜索功能，可用于定位插入点以维护排序顺序。提到的缺点适用。
在某些情况下，binary search tree 可能是排序数组的更好替代方案，用于维护 non-fixed 项的排序集。