代码之家 › 专栏 › 技术社区 › user9166703

二进制搜索递归调用数?

binary-search search java

user9166703 · 技术社区 · 7 年前

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

 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。

你能解释这是怎么回事吗?

1 回复 | 直到 7 年前

Michael Jeszenka 7 年前

只有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

此外,大O表示法是O(对数n)。在大O中,+1被认为是无关紧要的,因此不计算在内。请参见 this list 在Wikipedia上查看大O函数从最快到最慢的顺序。

推荐文章

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Laveen · python中的二进制搜索程序不会停止循环

7 年前

MEnnabah · 高效实现二进制搜索

7 年前

Tanay Choudhary · 如何为这个二进制搜索函数创建具有修改的最大/最小值的新数组

7 年前

user8742308 · 如果指定的数字位于排序数组的末尾或开头,则二进制搜索函数无法找到它们

7 年前

James Chavez · 二进制搜索查找不重复java的元素

7 年前

yrrah2 · 为什么我的二进制搜索使用这么多比较?

7 年前

James · 阻塞问题的一种算法设计[C++代码]

7 年前

Artemis · 为什么在二进制搜索中我们要除以2而不是其他更高的常数

7 年前

Johnny · 二进制搜索是贪婪算法吗?

7 年前