algorithm - 关于二进制搜索中的最坏情况

Question

二进制搜索的最坏情况是 1 + lg n，但是如果元素在排序数组中或元素不在排序数组中，这种更坏情况会改变吗？我认为应该通过更少的搜索来确定该元素不在数组中，或者搜索是否保持不变

Answer 1

假设您必须在最坏的情况下进行 k 比较，以便检查元素是否在数组中。在最后一次(kth)比较中，如果key不匹配，则元素显然不在数组中。因此，如果元素在 kth 比较后不在数组中，则无需再进行任何比较。

因此，无论元素是否在排序数组中，最坏的情况都应该保持不变，在 k=ceil(log(n))。

同样，在线性搜索的情况下，假设键位于​​数组的最后一个位置。我们需要 n 比较，如果数组的最后一个元素与键不匹配，我们可以断定该元素不在数组中。我们不需要任何更多的比较，最坏的情况将是相同的(在 n)，无论元素是否存在于数组中。