二分搜索的最坏情况是1 + lg n
,但是如果元素位于排序数组中或元素不在排序数组中,这种最坏情况会改变吗?我认为应该花费更少的搜索来确定该元素不在数组中,或者搜索保持不变
最佳答案
假设您必须在最坏的情况下进行 k
次比较才能检查该元素是否在数组中。在最后(kth
)比较中,如果键不匹配,则该元素显然不在数组中。因此,如果在第 k 次比较之后该元素不在数组中,则无需再进行任何比较。
因此,无论元素是否在排序数组中,最坏的情况都应该保持不变,k=ceil(log(n))
。
同样,在线性搜索的情况下,假设键位于数组的最后一个位置。我们需要n
次比较,如果数组的最后一个元素与键不匹配,我们可以断定该元素不在数组中。我们不需要更多的比较,无论数组中是否存在该元素,最坏的情况都是相同的(在 n
处)。
关于algorithm - 关于二分查找中最坏的情况,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41867265/