二进制搜索更糟糕的情况是 1 + lg n ，但是如果元素在排序数组中，或者如果元素不是't in it? I' m认为它应该花费更少的搜索来确定元素不在数组中，或者确实搜索保持不变
1 + lg n
假设您必须在最坏的情况下进行 k 比较，以检查元素是否在数组中 . 在最后一个（ kth ）比较中，如果键不匹配，则该元素显然不在数组中 . 因此，如果在 kth 比较之后元素不在数组中，则无需进行任何更多比较 .
k
kth
因此，最坏的情况应该保持不变，无论元素是否在排序数组中，在 k=ceil(log(n)) .
k=ceil(log(n))
同样，在线性搜索的情况下，假设密钥将位于数组的最后位置 . 我们需要 n 比较，如果数组的最后一个元素与键不匹配，我们可以得出结论，该元素不在数组中 . 我们不需要任何更多的比较，最坏的情况将是相同的（在 n ），无论数组中是否存在元素 .
n
1 回答
假设您必须在最坏的情况下进行
k比较，以检查元素是否在数组中 . 在最后一个（kth）比较中，如果键不匹配，则该元素显然不在数组中 . 因此，如果在kth比较之后元素不在数组中，则无需进行任何更多比较 .因此，最坏的情况应该保持不变，无论元素是否在排序数组中，在
k=ceil(log(n)).同样，在线性搜索的情况下，假设密钥将位于数组的最后位置 . 我们需要
n比较，如果数组的最后一个元素与键不匹配，我们可以得出结论，该元素不在数组中 . 我们不需要任何更多的比较，最坏的情况将是相同的（在n），无论数组中是否存在元素 .