Monday, January 3, 2011

Linear Search Shell Script


#!/bin/bash
# SCRIPT : linearsearch.sh
# USAGE : linearsearch.sh
# PURPOSE: Searches given number in a list.
# \\\\ ////
# \\ - - //
# @ @
# ---oOOo-( )-oOOo---
# A variation of Here Document permits "commenting out" data block.
: <<DATABLOCK

In computer science, linear search or sequential search is a method
for finding a particular value in a list, that consists in checking
every one of its elements, one at a time and in sequence, until the
desired one is found.

This is a very straightforward loop comparing every element in the
array with the key. As soon as an equal value is found, it returns.
If the loop finishes without finding a match, the search failed and
-1 is returned.

For small arrays, a linear search is a good solution because it's so
straightforward. In an array of a million elements, a linear search
will take,on average, 500,000 comparisons to find the key. For a much
faster search, take a look at binary search.

DATABLOCK

#####################################################################
# Define Functions Here #
#####################################################################

lsearch()
{
status=-1

for((i=0;i<count;i++))
do
Temp=$1

if [ $Temp -eq ${ARRAY[i]} ]
then

status=0
searches=$((i+1))
return

# return $((i+1))
# Bash function can return value between 0-255, That's why I assigned
# result to a global variable. This is one of the method to capture
# return value of a function.

fi

done
}

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

clear

echo "Enter Array Elements : "

read -a ARRAY

count=${#ARRAY[@]}

search=y

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

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

echo -n "Enter element to be searched : "
read num
lsearch $num

if [ $status -eq 0 ]
then
echo "$num found after $searches searches"
else
echo "$num not found"
fi

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

done

OUTPUT:
$ sh linearsearch.sh
Enter Array Elements :
12 34 56 78 90 23 45 56 67 321 66 88 92
Enter element to be searched : 56
56 found after 3 searches
Do you want another search (y/n): y
Enter element to be searched : 321
321 found after 10 searches
Do you want another search (y/n): y
Enter element to be searched : 100
100 not found
Do you want another search (y/n): n

2 comments:

  1. Perfect - just what I was looking for. Thank you!

    ReplyDelete
  2. thank you very much.
    You saved me for 2marrow test.

    keep posting.

    ReplyDelete