二分查找做了多少次遞歸函數調用？

Question

二分搜索是O（log2 N）。這是否意味着激活記錄堆棧的深度將是log2N？換句話說，有多少次遞歸函數調用？

Answer 1

是的，遞歸深度是O（log N）。你需要繼續打電話，直到你到達你的基本情況，這是個別的元素。但是，調用的確切數量取決於算法：有些在原子級別停止，有些在調用列表爲0時調用較深。它取決於列表長度，但確切數量取決於實現。