|
1
|
#!/bin/bash -e
|
|
2
|
. "$(dirname "${BASH_SOURCE[0]}")"/util.sh
|
|
3
|
|
|
4
|
if self_not_included; then
|
|
5
|
|
|
6
|
function binsearch() # usage: min=# max=# binsearch >_cmd args... (uses $i)
|
|
7
|
# because integer division truncates, $max is *exclusive*
|
|
8
|
{
|
|
9
|
echo_func; kw_params min max; : "${min?}" "${max?}"
|
|
10
|
local min="$min" max="$max" i iter_num=0
|
|
11
|
while true; do
|
|
12
|
log+ -2 echo_vars iter_num # it will always take log2(max - min) iters
|
|
13
|
|
|
14
|
i=$(( (min + max)/2 ))
|
|
15
|
log+ -2 echo_vars min max i
|
|
16
|
if ! (( i > min )); then break; fi
|
|
17
|
if echo_run "$@"; then min="$i"; else max="$i"; fi
|
|
18
|
|
|
19
|
((iter_num++)) || true
|
|
20
|
done
|
|
21
|
echo "$i"
|
|
22
|
}
|
|
23
|
alias binsearch='"binsearch" ' # last space alias-expands next word
|
|
24
|
|
|
25
|
fi
|
