非就地二分查找的时间复杂度
time complexity of non-inplace binary search
假设对长度约为 n/2 的子数组调用二分查找，并且在一个级别上最多有三个比较，我想出了 T(n) = T(n/2) + 3 作为递归关系。
但是：当我递归调用 binarySearch 时，切片的成本不是与 n 成正比吗？因此，解决方案不是 T(n) = nlogn 而不是 logn 吗？
这让我很困惑。我检查了 Python 的成本模型，并且（正如预期的那样）切片的成本与 n.
成正比
T(n) = T(n/2) + 3
log a / log b = 1
d = 1
因此
O(n) = O(log n)
一如既往，算法的复杂度及其实现可能存在差异。
如果您在递归函数中实现二分搜索，即获取输入数组的一部分的副本，则必须在 O(n) 中生成该数组，所以您是对的，这会导致O(n log n) 的总体复杂性（可能更糟，具体取决于您要复制的内容）。
所以你不应该这样实现。仅交出对数组的引用以及最小和最大索引值，以将搜索限制在您需要的数组部分。 （或类似的东西）
假设对长度约为 n/2 的子数组调用二分查找，并且在一个级别上最多有三个比较，我想出了 T(n) = T(n/2) + 3 作为递归关系。
但是：当我递归调用 binarySearch 时，切片的成本不是与 n 成正比吗？因此，解决方案不是 T(n) = nlogn 而不是 logn 吗？
这让我很困惑。我检查了 Python 的成本模型，并且（正如预期的那样）切片的成本与 n.
T(n) = T(n/2) + 3
log a / log b = 1
d = 1
因此
O(n) = O(log n)
一如既往，算法的复杂度及其实现可能存在差异。
如果您在递归函数中实现二分搜索，即获取输入数组的一部分的副本，则必须在 O(n) 中生成该数组，所以您是对的，这会导致O(n log n) 的总体复杂性（可能更糟，具体取决于您要复制的内容）。
所以你不应该这样实现。仅交出对数组的引用以及最小和最大索引值，以将搜索限制在您需要的数组部分。 （或类似的东西）