我为标准二进制搜索算法编写了这段递归代码。我只是想知道什么时候将 +1 添加到比较计数器？下面是伪代码
Inputs A: Array of Data;
key:Data; L,R:Integer;
Variables m:Integer;
Returns m:Integer;
Begin
If R<L then return -1; fi
m:= (R+L)/2
if key = A[m] then return m; fi
if key > A[m] then
return binSearch(A,key,m+1,R);
Else
return binSearch(A,key,L,m-1);
fi
End
检查第一个 if 语句中的 L 和 R 算作比较吗？有点困惑。
最佳答案
我相信，当您说比较时，您严格来说并不是指您有多少个 if，而是您试图达到二分查找的 O(log(n)) 复杂度？如果是这样，为什么不在函数的开头进行计数，这样您就可以计算调用的次数
关于algorithm - 二进制搜索比较次数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13794819/