为了更快速地搜索，难道不应该在进行二分搜索之前对数据应用合并排序，还是直接跳到线性搜索？
For faser searching, shouldn't one apply merge sort on the data before doing binary search or just jump straight to linear search?
我正在学习算法并且对它们在某些情况下的应用有疑问。有分治归并排序和二分查找。两者都比线性增长算法快。
假设我想在大量数据中搜索某个值。我不知道数据是否已排序。为什么不先进行归并排序，然后再进行二分查找，而不是进行线性搜索呢？那会更快吗？或者应用归并排序然后组合二分搜索的过程会比线性搜索更慢吗？为什么？是否取决于数据的大小？
如果列表的大小为 n，则
TimeOfMergeSort(list) + TimeOfBinarySearch(list) = O(n log n) + O(log n) = O(n log n)
TimeOfLinearSearch(list) = O(n)
O(n) < O(n log n)
暗示
TimeOfLinearSearch(list) < TimeOfMergeSort(list) + TimeOfBinarySearch(list)
当然，正如评论中提到的，排序频率和搜索频率在摊销成本中起着巨大的作用。
你的问题前提有问题。合并排序具有 O(N logN) 复杂度，这是任何基于比较的排序算法中最好的，但它仍然比单个线性扫描慢 lot。请注意 log2(1000) ~= 10。（显然，常数因子很重要 lot，尤其是对于较小的问题规模。线性搜索数组是 CPU 可以做的最有效的事情之一。为 MergeSort 复制东西并不坏，因为加载和存储来自顺序地址（因此缓存和预取是有效的），但它仍然是比读取数组 10 次要多得多。）
如果您需要支持混合 insert/delete 和查询操作，所有操作都具有良好的时间复杂度，请为任务选择正确的数据结构。二叉搜索树可能是合适的（或红黑树或其他一些进行某种重新平衡以防止 O(n) 最坏情况行为的变体）。那会给你 O(log n) 查询，和 O(log n) insert/delete.
排序数组给你 O(n) insert/delete （因为你必须将剩余的元素洗牌以制造或关闭间隙），但是 O(log n) 查询（具有较低的时间和 space 开销比一棵树）。
未排序数组：O(n) 查询（线性搜索），O(1) 插入（追加到末尾），O(n) 删除（O(n) 查询，然后洗牌元素以缩小差距）。高效删除接近末尾的元素。
链表，排序或未排序：除了简单之外没有其他优点。
哈希 table：insert/delete：O(1) 平均（摊销）。查询 present/not-present：O(1)。查询非现值介于哪个元素之间：O(n) 线性扫描跟踪大于 x 的最小元素和小于 x 的最大元素。
如果您的 inserts/deletes 发生在大块中，那么对新批次进行排序并进行合并排序比一次将一个元素添加到已排序的数组更有效。 （即插入排序）。在末尾添加一个块并进行快速排序也是一种选择，并且可能修改更少的内存。
因此最佳选择取决于您要优化的访问模式。
我正在学习算法并且对它们在某些情况下的应用有疑问。有分治归并排序和二分查找。两者都比线性增长算法快。
假设我想在大量数据中搜索某个值。我不知道数据是否已排序。为什么不先进行归并排序，然后再进行二分查找，而不是进行线性搜索呢？那会更快吗？或者应用归并排序然后组合二分搜索的过程会比线性搜索更慢吗？为什么？是否取决于数据的大小？
如果列表的大小为 n，则
TimeOfMergeSort(list) + TimeOfBinarySearch(list) = O(n log n) + O(log n) = O(n log n)
TimeOfLinearSearch(list) = O(n)
O(n) < O(n log n)
暗示
TimeOfLinearSearch(list) < TimeOfMergeSort(list) + TimeOfBinarySearch(list)
当然，正如评论中提到的，排序频率和搜索频率在摊销成本中起着巨大的作用。
你的问题前提有问题。合并排序具有 O(N logN) 复杂度，这是任何基于比较的排序算法中最好的，但它仍然比单个线性扫描慢 lot。请注意 log2(1000) ~= 10。（显然，常数因子很重要 lot，尤其是对于较小的问题规模。线性搜索数组是 CPU 可以做的最有效的事情之一。为 MergeSort 复制东西并不坏，因为加载和存储来自顺序地址（因此缓存和预取是有效的），但它仍然是比读取数组 10 次要多得多。）
如果您需要支持混合 insert/delete 和查询操作，所有操作都具有良好的时间复杂度，请为任务选择正确的数据结构。二叉搜索树可能是合适的（或红黑树或其他一些进行某种重新平衡以防止 O(n) 最坏情况行为的变体）。那会给你 O(log n) 查询，和 O(log n) insert/delete.
排序数组给你 O(n) insert/delete （因为你必须将剩余的元素洗牌以制造或关闭间隙），但是 O(log n) 查询（具有较低的时间和 space 开销比一棵树）。
未排序数组：O(n) 查询（线性搜索），O(1) 插入（追加到末尾），O(n) 删除（O(n) 查询，然后洗牌元素以缩小差距）。高效删除接近末尾的元素。
链表，排序或未排序：除了简单之外没有其他优点。
哈希 table：insert/delete：O(1) 平均（摊销）。查询 present/not-present：O(1)。查询非现值介于哪个元素之间：O(n) 线性扫描跟踪大于 x 的最小元素和小于 x 的最大元素。
如果您的 inserts/deletes 发生在大块中，那么对新批次进行排序并进行合并排序比一次将一个元素添加到已排序的数组更有效。 （即插入排序）。在末尾添加一个块并进行快速排序也是一种选择，并且可能修改更少的内存。
因此最佳选择取决于您要优化的访问模式。