1

I have a command cmd. cmd 1 succeeds, but cmd 10000000 fails.

cmd will succeed for all n < X, and fail for all n > X.

Is there a tool for doing binary search to find the value X?

1 Answer 1

2

I developed find-first-fail (https://codeberg.org/tange/tangetools/src/branch/master/find-first-fail) in bash. It can be called as a command:

find-first-fail cmd

Or can be sourced - in which case cmd can be a function:

. $(which find-first-fail)
find-first-fail cmd

find-first-fail first runs cmd 1. If that fails it will look for the minimal value where cmd succeeds. Else it will look for the minimal value where cmd fails.

So it will also find X if cmd 1 fails, and cmd 1000000 succeeds.

It does this using binary search: First it doubles the value until the exit code changes, then it does binary search between the last two values.

Simple example:

# Define a bash function that tries a guess and returns true if above the limit
# In this case it is easy to see the limit is 12345
# In normal use it will be used to probe a black box where it is hard to see the limit
guess() { [ "$1" -gt 12345 ] ; }
# Activate shell function
. find-first-fail
# Run guess
find-first-fail guess
# Show how searching is done:
find-first-fail -v guess
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .