Binarysearch Shell Script

 Binary search works by comparing an input value to the middle element
of the array. The comparison determines whether the element equals the
input, less than the input or greater. When the element being compared
to equals the input the search stops and typically returns the posit-
ion or number of searches of the element.  If the element is not equal
to the input and the element at the middle point is greater than the
input being searched, the current middle point becomes the new high
point and the array is cut in half again and re-tested. If the element
at the middle point is less than the input being searched, the current
middle point becomes the new low point and the array is cut in half
again and retested. This cutting in half and adjusting either the high
point or the low point is repeated until the item is found or the low
point and the high point converge. This is much faster then sequentia-
lly searching an entire array.

#!/bin/bash
# SCRIPT : binarysearch.sh
# USAGE  : binarysearch.sh
# PURPOSE: Searches given number in a sorted list.
#                         \\\\ ////
#                         \\ - - //
#                            @ @
#                    ---oOOo-( )-oOOo---
#
#####################################################################
#                      Define Functions Here                        #
#####################################################################

printnumbers()
{
  echo ${ARRAY[*]}
}

sortnumbers()                               # Using insertion sort
{
for((i=1;i<count;i++))
do
   Temp=${ARRAY[i]}
   j=$((i-1))
   while [ $Temp -lt ${ARRAY[j]} ]
   do
      ARRAY[j+1]=${ARRAY[j]}
      let j--
      if [ $j == -1 ]
      then
         break
      fi
   done
   ARRAY[j+1]=$Temp
done
}

binarysearch()
{
    status=-1
    i=1
    array=($(echo "$@"))
    LowIndex=0
    HeighIndex=$((${#array[@]}-1))

    while [ $LowIndex -le $HeighIndex ]
    do

        MidIndex=$(($LowIndex+($HeighIndex-$LowIndex)/2))
        MidElement=${array[$MidIndex]}

        if [ $MidElement -eq $SearchedItem ]
        then
            status=0
            searches=$i
            return
        elif [ $SearchedItem -lt $MidElement ]
        then
            HeighIndex=$(($MidIndex-1))
        else
            LowIndex=$(($MidIndex+1))
        fi

        let i++

    done
}

#####################################################################
#                       Variable Declaration                       #
#####################################################################

clear

echo "Enter Array Elements : "

read -a ARRAY

count=${#ARRAY[@]}

search=y

#####################################################################
#                       Main Script Starts Here                     #
#####################################################################

# sort the loaded array, must for binary search.
# You can apply any sorting algorithm. I applied insertion sort.

sortnumbers

echo "Array Elements After Sort: "

printnumbers

while [ "$search" == "y" -o "$search" == "Y" ]
do

     echo -n "Enter Element to be searched : "
     read SearchedItem
     binarysearch "${ARRAY[@]}"

     if [ $status -eq 0 ]
     then
         echo "$SearchedItem found after $searches searches"
     else
         echo "$SearchedItem not found in the list"
     fi

     echo -n "Do you want another search (y/n): "
     read search

done
OUTPUT:

[venu@localhost shell]$ chmod 755 binarysearch.sh
[venu@localhost shell]$ ./binarysearch.sh
Enter Array Elements :
12 34 56 21 43 11 -32 87 112 -43 -111 98 100 22 0 11
Array Elements After Sort:
-111 -43 -32 0 11 11 12 21 22 34 43 56 87 98 100 112
Enter Element to be searched : 21       # Middle element
21 found after 1 searches
Do you want another search (y/n): y
Enter Element to be searched : 112
112 found after 5 searches
Do you want another search (y/n): y
Enter Element to be searched : 56       # second middle element(upper)
56 found after 2 searches
Do you want another search (y/n): y
Enter Element to be searched : 0        # second middle element(lower)
0 found after 2 searches
Do you want another search (y/n): y
Enter Element to be searched : -111
-111 found after 4 searches
Do you want another search (y/n): n