java - 二分查找递归调用次数？

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

 }

其中表示“如果元素个数n是2的幂，则将n表示为2的幂...情况3:键不在数组中，其值在a[0]和a[n-1]之间。这里判断键不在数组中的比较次数等于指数，比最坏的情况少比较一次。”

但是当我坐下来发现使用数组 {1,2,3,4,5,6,7,9} 和键 8 的函数调用次数时，调用次数是 4。书上说比较的次数是 3(不包括我猜的第三行？)，但我很确定函数调用的次数是 4。我还将其推广到二分搜索的迭代实现，并推广了迭代次数或递归函数调用次数始终为 Floor(log base 2 ( n ) ) + 1。

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

Answer 1

仅 3 target == arr[mid]进行比较。在第四次迭代中，基本情况 if(low > high)已达到，因此从不进行比较。正如您所说:“这里确定键不在数组中的比较次数等于指数。”你是对的，我们不处理第 3 行的比较语句。我们只关心目标值的比较语句。

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

二分搜索8在数组 {1,2,3,4,5,6,7,9}

第一次迭代:

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在 Wikipedia 上了解 Big O 函数从最快到最慢的顺序。