二进制搜索最后一个元素，当它是 2 的幂时

Question

我有一个排序数组。

例如。 { 1, 2, 3, 4, 5 ,6, 7, 8 }

如果我搜索元素 8，则需要 4 次迭代才能得到结果为真或假。我所知道的是 运行 二进制搜索的时间上限为 O(logn)，在这种情况下结果为 3。

如果我错了，有人可以帮我解决这个困惑或纠正我的概念吗？

我的代码如下：

public static boolean BinarySearch(int[] arr, int num){    
int mid, low, high;    
int count = 0;    
low = 0; high = arr.length -1;    
while( low <= high ){    
mid = low + (high-low)/2;    
if(arr[mid] == num)    
      return true;    
else if(arr[mid]<num)    
     low = mid +1;    
else
     high = mid -1;    
}    
return false;    
}

Answer 1

O 符号的要点是隐藏不太重要的术语，以便为复杂性得出更简单的表达式。因此，尽管二分查找的复杂度是 O(lg n) 是正确的，但准确的表达式很可能是 ceil(lg n) + 1，甚至 c ceil(lg n) + b 对于任何 c 和 b（ ceil() 操作对于始终从对数中得到整数结果是必要的。