二分查找做了多少次递归函数调用？

Question

二分搜索是O（log2 N）。这是否意味着激活记录堆栈的深度将是log2N？换句话说，有多少次递归函数调用？

Answer 1

是的，递归深度是O（log N）。你需要继续打电话，直到你到达你的基本情况，这是个别的元素。但是，调用的确切数量取决于算法：有些在原子级别停止，有些在调用列表为0时调用较深。它取决于列表长度，但确切数量取决于实现。