单调函数中的第一个严格更大的元素
First strictly greater element in a monotone function
我有函数 f:N->Z，其中 f(i) < f(i+1) 对于每个 i。
目标是建议找到 n = min{ i | 的算法f(i) > 0 } 在 O(log n) 中。
-调用函数f(i)算作基本操作。
O(log n) 建议使用二分查找，但我不知道使用什么作为上限。
任何关于如何解决这个问题的建议都将不胜感激。
编辑：
问题类似于在排序数组中找到第一个严格更大的元素，不同之处在于这里我有数组的函数 insted，所以我没有上限。
问题更多的是理论上的，我不需要实施解决方案。
如果您知道 n 的最大值，您可以简单地从区间 [0,max] 开始，然后进行二分查找。
如果 n 是无界的，您可以尝试在 f(i) > 0.
中找到任何 i
步骤 1： 找到有效上限：
尝试 i=1, 2, 4, 8, 16, 32, ... 直到你找到一个带有 f(i) > 0 的 i （需要 O(log n) 次尝试）
步骤 2： 使用 [0, iupperBound] 进行二分查找（需要 O(log n) 时间）
所以总体时间复杂度是O(log n)
我有函数 f:N->Z，其中 f(i) < f(i+1) 对于每个 i。
目标是建议找到 n = min{ i | 的算法f(i) > 0 } 在 O(log n) 中。
-调用函数f(i)算作基本操作。
O(log n) 建议使用二分查找，但我不知道使用什么作为上限。
任何关于如何解决这个问题的建议都将不胜感激。
编辑：
问题类似于在排序数组中找到第一个严格更大的元素，不同之处在于这里我有数组的函数 insted，所以我没有上限。
问题更多的是理论上的，我不需要实施解决方案。
如果您知道 n 的最大值，您可以简单地从区间 [0,max] 开始，然后进行二分查找。
如果 n 是无界的，您可以尝试在 f(i) > 0.
i
步骤 1： 找到有效上限：
尝试 i=1, 2, 4, 8, 16, 32, ... 直到你找到一个带有 f(i) > 0 的 i （需要 O(log n) 次尝试）
步骤 2： 使用 [0, iupperBound] 进行二分查找（需要 O(log n) 时间）
所以总体时间复杂度是O(log n)