我在理解一些更高级的排序、选择、搜索等算法方面取得了一些很好的突破。
然而，这是我坚持的场景。
对于要在其中查找第 k 个最小元素的值数组，如果未排序，则可以使用 quickselect，如果已排序，则可以使用二分查找。
如果我理解正确，通过枢轴/分区系统，快速选择将通过选择枢轴来搜索未排序的数据集，通过将每个元素与枢轴进行比较来创建低点和高点组，然后通过更改递归地将列表分解为子列表枢。
这听起来与二进制搜索的工作方式非常相似，那么为什么快速选择适用于未排序的值而二进制搜索却没有，并且不是快速选择算法中的所有比较（计算出低点和高点）都需要一个很多...成本？
二分搜索不能确定第k个最小的元素：它不是选择算法。二进制搜索确定您作为输入提供的值是否在数组中。
选择算法确定第k个最小的元素。如果数组已经排序，就像二分查找一样，那么选择第k个最小的元素可以在O(1)中完成，只需使用k作为数组的索引。
回顾一下：使用快速选择，您可以确定例如数组中的第 8 个最小元素，而使用二分搜索，您可以搜索值 15 的元素是否在数组中。
快速选择可以在预期的O(n)时间内选择任意顺序统计；二进制搜索可以在O(log n)时间内搜索到一个元素，但需要对数组进行排序，否则算法将不正确。正如我告诉你的，选择排序数组中的第k个最小元素是微不足道的，需要O(1)时间来访问排序数组中的第k个元素。
最后，在数组未排序时搜索元素（给定值）在最坏的情况下需要O(n)时间，因为您需要对数组执行线性扫描。