バイナリ検索で何回再帰関数呼び出しを行うのですか？

Question

バイナリ検索はO（log2 N）です。これは、アクティベーションレコードのスタックの深さがlog2 Nになることを意味しますか？言い換えれば、いくつの再帰関数呼び出しが行われますか？

Answer 1

はい、再帰の深さはO（log N）です。個々の要素であるベースケースに到達するまで、通話を続ける必要があります。ただし、呼び出しの正確な量はアルゴリズムに依存します。あるものは原子レベルで停止します。あるものは、渡されたリストが0のときに深く呼び出します。リストの長さによって異なりますが、正確な数は実装によって異なります。