Search code examples
algorithmsearchfindcomputer-science

First strictly greater element in a monotone function

I have function f:N->Z where f(i) < f(i+1) for every i.

Goal is to sugest algoritam that finds n = min{ i | f(i) > 0 } in O(log n).

-calling function f(i) counts as basic operation.

O(log n) suggest using binary search but I'm having trouble what to use as upper bound.

Any suggestions on how to approach this would be appreciated.

Edit:

Problem is similar as finding first strictly greater element in a sorted array, difference being that here I have function insted of array so I dont have upper bound.

Question is more for theory, I dont need to implement solution.

Solution

  • If you know a maximal value for n, you could simply start with the interval [0,max] and proceed with a binary search.

    If n is unbounded you can try to find any i where f(i) > 0.

    Step 1: find a valid upper bound:
    try i=1, 2, 4, 8, 16, 32, ... until you found an i with f(i) > 0 (takes O(log n) tries)

    Step 2: binary search with [0, iupperBound] (takes O(log n) time)

    So overall time-complexity is O(log n)