二进制搜索递归调用次数？

Question

所以我想知道，在我的书中，递归二分查找是这样实现的：

 private static int bin(int[] arr, int low, int high, int target){
     counter++; //ignore this, it was to count how many calls this function invocated
     if(low > high) return -1;
     else{
         int mid = (low+high) / 2;
         if(target == arr[mid]) return mid;
         else if(target < arr[mid]) return bin(arr, low, mid-1, target);
         else return bin(arr, mid + 1, high, target);
     }

 }

它说 "If n, the number of elements, is a power of 2, express n as a power of 2... Case 3: The key is not in the array, and its value lies between a[0] and a[n-1]. Here the number of comparisons to determine that the key is not in the array is equal to the exponent. There will be one fewer comparison than in the worst case."

但是当我坐下来发现使用数组{1,2,3,4,5,6,7,9}和键8的函数调用次数时，调用次数是4次。书上说 COMPARISONS 的数量是 3（这不包括我猜的第 3 行？），但我很确定函数调用的数量是 4。我还将其概括为二进制搜索的迭代实现并概括了迭代次数，或递归函数调用，总是 floor(log base 2 ( n ) ) + 1.

可以解释一下这是怎么回事吗？

Answer 1

只进行了 3 target == arr[mid] 次比较。在第四次迭代中达到基本情况 if(low > high)，因此永远不会进行比较。正如您所说："Here the number of comparisons to determine that the key is not in the array is equal to the exponent."您是正确的，因为我们没有处理第 3 行的比较语句。我们只关心目标值的比较语句。

让我们看看迭代，直到达到 2 个基本情况中的任何一个。

在数组 {1,2,3,4,5,6,7,9}

中二进制搜索 8

第一次迭代：

low = 0
high = 7
mid = 3
arr[mid] = 4
(target == arr[mid]) == false

第二次迭代：

low = 4
high = 7
mid = 5
arr[mid] = 6
(target == arr[mid]) == false

第三次迭代：

low = 7
high = 7
mid = 7
arr[mid] = 7
(target == arr[mid]) == false

第四次迭代：

low = 8
high = 7
low > high == true

此外，大 O 表示法是 O(log n)。 + 1 在 Big O 中被认为是微不足道的，因此不计算在内。请参阅维基百科上的 this list，了解 Big O 函数从最快到最慢的顺序。

二进制搜索递归调用次数？

Binary search recursive number of calls?

java

search

binary-search