我有一些很好的突破，了解一些更先进的排序，选择，搜索等算法 .
这是我坚持的情景 .
对于要在其中查找第k个最小元素的值数组，可以使用quickselect（如果未排序）和二进制搜索（如果已排序） .
如果我理解正确的话，通过枢轴/分区系统，quickselect将搜索未排序的数据由通过改变选择一个支点，每个元素比较枢轴创造的低点和高点的组，然后递归打破名单成子列表设置枢 .
这听起来非常相似，二进制搜索是如何工作的，那么，为什么上无序值quickselect工作和二进制搜索不，不全部在quickselect算法相比（摸出低点，高点）取很多......成本？
1 回答
二进制搜索不确定第k个最小元素：它不是选择算法 . 二进制搜索确定您作为输入提供的值是否在数组中 .
选择算法确定第k个最小元素 . 如果数组已经排序，如二进制搜索的情况，那么选择第k个最小元素可以在O（1）中完成，只需使用k作为数组的索引 .
回顾一下：使用quickselect，您可以确定例如数组中的第8个最小元素，而使用二进制搜索，您可以搜索值为15的元素是否在数组中 .
Quickselect可以在预期的O（n）时间内选择任意顺序统计;二进制搜索可以在O（log n）时间内搜索元素，但需要对数组进行排序，否则算法将不正确 . 正如我告诉你的那样，选择排序数组中的第k个最小元素是微不足道的，需要O（1）时间来访问排序数组中的第k个元素 .
最后，在未对数组进行排序时搜索元素（给定值），在最坏的情况下需要O（n）时间，因为您需要对数组执行线性扫描 .