3
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

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))
\$\endgroup\$
1
  • \$\begingroup\$ Thank you! This increased performance and elegance of my code! \$\endgroup\$
    – theoden8
    Jul 26, 2015 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.