Central Download

Binarysearch Shell Script

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

Available link for download

Posted by Unknown at 1:22 PM

Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest

Labels: binarysearch, script, shell