Revision 9563
Added by Aaron Marcuse-Kubitza about 11 years ago
| binsearch.sh | ||
|---|---|---|
| 7 | 7 |
# because integer division truncates, $max is *exclusive* |
| 8 | 8 |
{
|
| 9 | 9 |
echo_func; kw_params min max; : "${min?}" "${max?}"
|
| 10 |
local min="$min" max="$max" i |
|
| 10 |
local min="$min" max="$max" i iter_num=0
|
|
| 11 | 11 |
while true; do |
| 12 |
log+ -2 echo_vars |
|
| 12 |
log+ -2 echo_vars iter_num # it will always take log2(max - min) iters
|
|
| 13 | 13 |
|
| 14 | 14 |
i=$(( (min + max)/2 )) |
| 15 | 15 |
log+ -2 echo_vars min max i |
| 16 | 16 |
if ! (( i > min )); then break; fi |
| 17 | 17 |
if echo_run "$@"; then min="$i"; else max="$i"; fi |
| 18 |
|
|
| 19 |
((iter_num++)) || true |
|
| 18 | 20 |
done |
| 19 | 21 |
echo "$i" |
| 20 | 22 |
} |
Also available in: Unified diff
lib/sh/binsearch.sh: binsearch(): also echo_vars the iter_num, to track how close binsearch is to finding the value (it will always take the same # iters, log2(max - min) )