二进制搜索递归调用次数？-Java 学习之路

所以我想知道，在我的书中，递归二进制搜索实现如下：

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);
     }

 }

并且它说“如果n，元素的数量，是2的幂，表示n为2的幂...情况3：键不在数组中，其值介于[0]和a [n-1] . 这里确定键不在数组中的比较次数等于指数 . 与最坏的情况相比，比较少一次 . “

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

可以解释一下这里发生了什么吗？

1 回答

0
只进行了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
```
此外，Big O表示法是O（log n） . 1在大O中被认为是微不足道的，因此不计算在内 . 有关Big O功能从最快到最慢的顺序，请参阅维基百科上的this list .
回复于 2024-04-24T04:04:24+08:00

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

1 回答

相关问题