递归二分搜索的函数调用次数相关技术问题

Great question about recursive binary search call counts—let's break this down clearly, especially for when your array size n is a power of 2 (like 2, 4, 8, 16, etc.). Your counter increments every time the bin function runs, so we'll count every single invocation including the initial call and all recursive ones.

1. Unsuccessful Search (Target Not in Array) #

This is the most predictable scenario. When the target isn't present, we keep splitting the array until we hit the low > high base case—meaning we traverse every level of the binary search tree plus one final call that triggers the base case.

For n = 2^k (where k is a non-negative integer):

• The binary search tree has k + 1 levels (e.g., n=8=2^3 has 4 levels: 0-7, 0-2/3-7, 0-0/1-2/3-5/6-7, etc.)
• Total function calls will be k + 2 (or equivalently, log2(n) + 2).

Example: n=8 (k=3), target larger than all elements #

• Call 1: bin(arr, 0,7, target) → mid=3, target not found
• Call 2: bin(arr, 4,7, target) → mid=5, target not found
• Call 3: bin(arr, 6,7, target) → mid=6, target not found
• Call 4: bin(arr,7,7, target) → mid=7, target not found
• Call 5: bin(arr,8,7, target) → low>high, return -1
  Total calls: 5 = 3 + 2 = log2(8)+2

2. Successful Search (Target Exists in Array) #

Here, the number of calls depends entirely on where the target lives in the array:

Best Case (Target is the Middle Element) #

We find the target on the very first call. Total calls: 1 (just the initial invocation).

Worst Case (Target is at a Leaf Node) #

The target sits in one of the "deepest" positions of the binary search tree. For n=2^k, this requires traversing all k levels down to the leaf. Total calls: k (or log2(n)).

Example: n=8 (k=3), target at index 0 #

• Call 1: bin(arr,0,7, target) → mid=3, target < arr[3]
• Call 2: bin(arr,0,2, target) → mid=1, target < arr[1]
• Call 3: bin(arr,0,0, target) → mid=0, target found
  Total calls: 3 = log2(8)

Average Case #

Across all possible target positions:

• 1 element (the root/middle) takes 1 call
• 2 elements take 2 calls
• 4 elements take 3 calls
• ...
• 2^{k-1} elements take k calls

The total number of calls across all positions is (k-1)*2^k + 1. Dividing by n=2^k gives the average:
(k-1) + 1/2^k → which simplifies to log2(n) - 1 + 1/n

For n=8, this works out to 3-1 + 1/8 = 2.125 calls on average.

Quick Summary Table (n=2^k) #

内容的提问来源于stack exchange，提问作者user9166703