algorithm - 二分搜索比较次数

Question

我为标准二进制搜索算法编写了这段递归代码。我只是想知道何时将 +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 算作比较吗？有点困惑。

Answer 1

我相信，当您说比较时，您并不意味着严格地说您有多少个 if，而是您试图达到二进制搜索的 O(log(n)) 复杂性？如果是这样，为什么不在函数的开头计算，以便计算调用的数量

Answer 2

在渐近分析中，条件语句被认为是 O(1)。

因为条件问题是决策问题。0 或 1。