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