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))