所以我想知道，在我的书中，递归二进制搜索的实现方式如下：
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。
可以解释这里发生了什么吗？
仅进行了3个target == arr[mid]比较。在第四次迭代中，if(low > high)已达到基本情况，因此从未进行比较。如您所述：“这里确定键不在数组中的比较次数等于指数。” 您是正确的，因为我们不处理第3行的比较语句。我们只关心目标值的比较语句。
让我们看一下迭代，直到达到两种基本情况之一。
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
同样，Big O表示法是O（log n）。在大O中+ 1被认为无关紧要，因此不算在内。请参阅Wikipedia上的此列表，以了解Big O功能从最快到最慢的顺序。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句