这个伪代码的 Big-O 是什么？我也需要一个适当的解释

Question

这是我想计算时间复杂度的伪代码，我认为它是一个二进制搜索算法，但我在计算复杂度时失败了，因为它减少了对数。

   USE variables half-array,found,middle element
   SET half-array=initial array;
   SET found=True;

 Boolean SearchArray(half-array)

   find middle element in half-array;
   Compare search key with middle element;
   IF middle element==search key THEN
           SET found=True;
   ELSE
        IF search key< middle element THEN
          SET half-array=lower half of initial array;
        ELSE
          SET half-array=upper half of initial array;


 SearchArray(half-array)

Answer 1

看起来你是运行递归地使用这个方法，并且每次迭代你都会将搜索的元素数量减少一半。这将是对数减少，即 O(log n).

由于每次都将元素减少一半，因此您需要确定将其减少为单个元素需要执行多少次，this previous answer provides a proof or if you are a more visual person, you can use the following diagram from this response:

Answer 2

是的，这确实是一个二进制搜索 algorithm.The 之所以称为 'binary' 搜索是因为，如果你注意到，在每次迭代之后，你的问题 space大约减少了一半（我说大概是因为 floor 函数）。所以现在，为了找到复杂度，我们必须设计一个递推关系，我们可以用它来确定二分搜索的最坏情况下的时间复杂度。

令 T(n) 表示二分查找对 n elements.In 最坏情况下的比较次数，没有元素是 found.Also，为了使我们的分析更容易，假设 n 是一个幂共 2

二进制搜索：

只有一个元素时，只有一个检查，因此T(1) = 1。
它计算中间条目然后将它与我们的key.If比较它等于键，它returns索引，否则它通过更新upper和下限使得 n/2 个元素在范围内。
然后我们只检查两半中的一个，这是递归完成的，直到剩下一个元素。

因此，我们得到递归关系：

T(n) = T(n/2) + 1

利用主定理，我们得到时间复杂度为T(n) ∈ Θ(log n)

另请参阅：Master Theorem

Answer 3

您说此算法是二进制搜索是正确的（将您的伪代码与此维基百科页面上的伪代码进行比较：Binary Search）

既然如此，该算法的最坏情况时间复杂度为 O(log n)，其中 n 是给定数组中元素的数量。这是因为在每次找不到目标元素的递归调用中，都会将数组分成两半。

这个缩减过程是对数的，因为在这个算法结束时，您将仍然需要检查的元素数除以 2（您这样做的次数），从而将列表缩减为单个元素大致等于（见下文）您必须将 2 自乘以获得等于给定数组大小的数字的次数。

*我在上面说大致因为递归调用的次数总是一个整数值，而你必须提高 2 的幂不会是一个整数如果给定列表的大小不是 2 的幂，则为整数。

这个伪代码的 Big-O 是什么？我也需要一个适当的解释

What is the Big-O of this pseudo code? I need a proper explain also

java

algorithm

big-o

pseudocode