二分搜索与简单搜索
Binary search vs simple search
根据算法书籍，二分搜索的性能为 O(log n)，而简单搜索为 O(n)。
但为什么我们不考虑排序所花费的时间，这是二分查找的先决条件？
假定数据将存储已排序。由于每次执行搜索时数据不需要 re-sorted，因此不会在 Big O 中计算。
简而言之：因为通常构建该列表只进行一次，而搜索（和更新）则进行多次。
构建排序列表确实需要 O(n log n)。使用二分查找的要点是，一旦集合排序，我们就可以对该列表执行 多个 查询，每个查询 O(log n) .
此外，如果您使用二叉搜索树，您也可以在 O(log n) 中执行插入和删除元素，因此 更新 集合也可以很便宜（前提是您为此使用了有效的数据结构）。
例如，在数据库中，人们经常使用索引来执行快速查找。通常读取的数量比更新的数量大。更新单个元素需要 O(log n)，因此在现有数据上创建索引确实很昂贵，但与搜索和更新 B-tree datastructure [wiki] 相比，这不是很常见。
根据算法书籍，二分搜索的性能为 O(log n)，而简单搜索为 O(n)。
但为什么我们不考虑排序所花费的时间，这是二分查找的先决条件？
假定数据将存储已排序。由于每次执行搜索时数据不需要 re-sorted，因此不会在 Big O 中计算。
简而言之：因为通常构建该列表只进行一次，而搜索（和更新）则进行多次。
构建排序列表确实需要 O(n log n)。使用二分查找的要点是，一旦集合排序，我们就可以对该列表执行 多个 查询，每个查询 O(log n) .
此外，如果您使用二叉搜索树，您也可以在 O(log n) 中执行插入和删除元素，因此 更新 集合也可以很便宜（前提是您为此使用了有效的数据结构）。
例如，在数据库中，人们经常使用索引来执行快速查找。通常读取的数量比更新的数量大。更新单个元素需要 O(log n)，因此在现有数据上创建索引确实很昂贵，但与搜索和更新 B-tree datastructure [wiki] 相比，这不是很常见。