2
$\begingroup$

Given a lower-bound predicate function which returns true if an input is greater than or equal to a constant string, what is the optimal way to search for the constant? The strings should be lexicographical compared.

For example, given a handle to the following function, but not knowing the specific constant used:

fn lower_bound(s: &[u8]) -> bool {
    s >= &[10, 20, 30]
}

What is the optimal algorithm for determining the enclosed value of &[10, 20, 30]? A maximum length for the value can be assumed if that makes it more tractable.

$\endgroup$
2
$\begingroup$

The most optimal algorithm would be to perform a binary search for each character sequentially (bin-search for 1st char, bin-search for 2nd char, ...etc).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.