Wednesday, October 27, 2021

[SOLVED] Why is the execution of my binary search script not proceeding after input?

Issue

I wrote a shell script for binary search of integers. It's accepting space separated integer array, but when the code proceeds and we input the element to be searched, the code doesn't proceed further. It is either stuck or it is accepting more inputs, both of which is undesired.

Here's the code:

#!/bin/bash

declare -a arr
echo "Enter space separated sorted integers:"
read -ra arr

declare -i search
echo -n "Enter the element to be searched for: "
read -r search

index=-1
beg=0
mid=0
last=${#arr[@]}
last=$((last - 1))

while [ $beg -le $last ]; do
    mid=$((beg / 2 + end / 2))
    if [ $mid -eq "$search" ]; then
        index=$mid
        break
    elif [ $mid -gt "$search" ]; then
        end=$((mid - 1))
    elif [ $mid -lt "$search" ]; then
        beg=$((mid + 1))
    fi
done

if [ $index -ne -1 ]; then
    echo "Element found at $index"
else
    echo "Element not found"
fi

Solution

Ok, so here are the errors I found in my code:

  1. using end instead of last (Thanks to John Kugelman, EdmCoff, markp-fuso)
  2. Never actually comparing Array values as in Array[index] (Thanks to markp-fuso)
  3. sometimes, mid=$((beg / 2 + last / 2)) won't behave as mid=(beg + last)/2. Sometimes when beg, last=5, beg/2 + last/2 will evaluate in 4 instead of 5.
  4. Last but not least, using echo in debugging always helps, (Thanks to chepner )

So final working code looks like:

#!/bin/bash

declare -a arr
echo "Enter space separated sorted integers:"
read -ra arr

declare -i search
echo -n "Enter the element to be searched for: "
read -r search

index=-1
beg=0
mid=0
last=${#arr[@]}
last=$((last - 1))

while [ $beg -le $last ]; do
    echo -e "\nbeg=$beg\nmid=$mid\nlast=$last\n"
    mid=$((beg + last))
    mid=$((mid/2))
    if [ "${arr[$mid]}" -eq "$search" ]; then
        index=$mid
        break
    elif [ "${arr[$mid]}" -gt "$search" ]; then
        last=$((mid - 1))
    elif [ "${arr[$mid]}" -lt "$search" ]; then
        beg=$((mid + 1))
    fi
done

if [ $index -ne -1 ]; then
    echo "Element found at $((index+1))"
else
    echo "Element not found"
fi


Answered By - infinitEplus
at