Finding the smallest integer such that a given condition holds with "binary search"

Question

Setup. Suppose we are given a function $$f:\mathbb N\to\{\text{False},\text{True}\}$$ such that $$f(n)=\text{True}\implies f(n+1)=\text{True}$$ and such that $f(n)=\text{True}$ for some $n$ large enough.

In natural language. The function $f$ imposes a condition on the natural numbers which is fulfilled once $n$ is large enough.

My question 1. How can I, for any given $f$, find the smallest $n$ such that $f(n)=\text{True}$?

A first idea would be to start with $n=1$ and to increment $n$ by one until $f(n)$ is True. However, this is fairly slow. The next step is a "binary search" algorithm (see below).

My question 2. How can I implement a good algorithm in Mathematica?

Here is an example of the first algorithm that I thought of, implemented in Python:

def bin_search(cond):
    n = 1
    while not cond(n):
        n *= 2
    lower_bound = n//2
    upper_bound = n
    middle = (lower_bound + upper_bound)//2
    while upper_bound - lower_bound > 1:
        if cond(middle):
            upper_bound = middle
        else:
            lower_bound = middle
        middle = (lower_bound + upper_bound)//2
    return upper_bound

---

For example, one such condition would be $$f(n)=[H_n\geq 10],$$

where $$H_n=\sum_{i=1}^n \frac 1i$$ is the $n$th harmonic number.

EDIT: A remark about the harmonic numbers: In fact I wanted to compare the runtime of a good brute force method against an intelligent method for this problem. For solving $H_n\geq 10$, it suffices to find the smallest integer $n$ such that $$\ln(n)+\gamma\geq 10,$$ where $\gamma$ denotes the Euler-Mascheroni constant. So we can find $$n=[ \exp(10-\gamma)],$$ where $[\cdot]$ denotes the nearest integer function.

Answer 1

Here is one implementation of your algorithm:

firstTrue[f_] := next[f, 1, Infinity]

next[f_, last_, cur_] := If[last + 1 == cur,
    If[f[last], last, cur],
    If[f[last], next[f, dec[last], last], next[f, inc[last], cur]]
]

inc[n_] := With[{e = IntegerExponent[n, 2]},
    If[n == 2^e, 2^(e+1), n + 2^(e-1)]
]

dec[n_] := With[{e = IntegerExponent[n, 2]},
    If[n == 2^e, 2^(e-1) + 2^(e-2), n - 2^(e-1)]
]

Your example:

firstTrue[HarmonicNumber[#] >= 10&]

12367

Of course, for analytic functions like HarmonicNumber there are much better algorithms to do this.

Answer 2

As Carl Woll says:

Of course, for analytic functions like HarmonicNumber there are much better algorithms to do this.

Here is some code related to that statement -- it uses one of the universal WL functions:

Clear[H];
H[n_] := Sum[1/i, {i, n}];

FindArgMin[{H[n], H[n] >= 10, n > 0}, n]
(* {12366.5} *)

N@H[Ceiling[%[[1]]]]
(* 10. *)

N@H[Floor[%%[[1]]]]
(* 9.99996 *)