Shell binary search with sorted input

Question

I have coded binary search in shell, just for practice.

Input

Input data is already sorted set of numbers streamed to the script. 1ドル is the sought number.

for i in {1..1000000}; do
 echo $RANDOM
done | sort -n | ./binsearch.ksh 10

Code

I use ksh as the fastest shell against bash, zsh and other bash clones, and as an interpreter that maintains lists - against dash.

Variables: puppy is the sought number; swamp is a sorted set of numbers.

#!/bin/ksh
puppy=1ドル; [ -z "$puppy" ] && {
 echo "@@@ No args specified."
 exit
}
size=0
while IFS= read -r line; do
 ((++size))
 swamp[${#swamp[*]}]=$line
done
echo
left=0
right=$(($size - 1))
while [ $left -le $right ] ; do
 mid=$((($left + $right) >> 1))
# echo "$left $mid(${swamp[$mid]}) $right"
 if [ $puppy -eq ${swamp[$mid]} ]; then
 echo "$puppy $mid"
 exit
 elif [ $puppy -lt ${swamp[$mid]} ]; then
 right=$(($mid - 1))
 else
 left=$((mid + 1))
 fi
done
echo '</not found>'

Could you please tell what you think of this code and how can I improve it?

Note

I would care about POSIX compatibility if it was a chance to have lists in dash, but as far as there's none, I would have to use namespaces with eval and get my memory filled with 1e6 swamp_43254-like variables.

Answer 1

It's pretty cool to be able to do this in Bash.

Input validation

There are several issues here:

puppy=1ドル; [ -z "$puppy" ] && {
 echo "@@@ No args specified."
 exit
}

Code is most readable when there is one statement per line, so I suggest to separate the variable assignment and the input validation steps.

exit without arguments exits with the code of the last command, in this case 0 because the echo most probably succeeds, so the program exits with success. But it shouldn't. A common practice is to use exit code 2 for invalid usage.

Lastly, instead of not-valid-and-exit I think valid-or-else-exit is a somewhat cleaner logic, and also simpler to write:

puppy=1ドル
[ "$puppy" ] || {
 echo "@@@ No args specified."
 exit 2
}

Unnecessary $size

The size variable is unnecessary. You can use ${#swamp[*]} instead, for example in:

right=$((${#swamp[*]} - 1))

Unnecessary $ inside $((...))

You can simplify these:

mid=$((($left + $right) >> 1))
right=$(($mid - 1))

Like this:

mid=$(((left + right) >> 1))
right=$((mid - 1))

• theoden8: Thank you! This increased performance and elegance of my code!