Program To Implement Binary Search Using Shell Programming

0
507

Writing a shell script for binary search is easy if we have the right idea about this search technique. First let us discuss about binary search. It is used to find the position of an element from an array of sorted numbers. The middle element of the sorted array is marked first. The element to be found is considered as the input key. Set the lower bound as well as the upper bound of the elements. So when we have to find the position of a specific number, check whether it is greater than the middle element of the array. If yes, the binary search is performed on the right sub-array. But if the element is less than the element in the mid value, check in the left sub-array.

The best case performance of binary search algorithm = O(1)

The worst case performance of binary search algorithm= O(log n)

shell-script


ALGORITHM

Step 1: Start

Step 2: Enter the limit and read  it to n

Step 3: Enter the elements using for loop..

Step 4: for i equal to zero, i<n and  i++  read value to m .assign these values to array a[i].echo the array

Step 5: for i=1, i<n, i++ and for  j=0,j<n-i,j++ , check if a[j] is greater than a[j+1].If so do the following

Step 6: Assign value of a[j] to t, a[j+1] to a[j] and t to a[j+1].

Step 7: Echo the sorted array

Step 8: Enter the element to be searched and read it to s.

Step 9: Initialize l=0,c=0 and u=n-1

Step 10: While l less than or equal to u calculate mid value by (l+u )/2

Step 11: check if s is equal to a[mid] value, if so assign c=1 and break.

Step 12: else if check whether s is less than a[mid].if so assign value of u as (mid-1) else   l as (mid+1).

Step 13: If c is equal to 1 echo element found at position mid +1 else not found.

Step 14: Stop

Binary search using shell script

echo “Enter the limit:”

read n

echo “Enter the numbers”

for(( i=0 ;i<n; i++ ))

do

read m

a[i]=$m

done

for(( i=1; i<n; i++ ))

do

for(( j=0; j<n-i; j++))

do

if [ ${a[$j]} -gt ${a[$j+1]} ]

then

t=${a[$j]}

a[$j]=${a[$j+1]}

a[$j+1]=$t

fi

done

done

echo “Sorted array is”

for(( i=0; i<n; i++ ))

do

echo “${a[$i]}”

done

echo “Enter the element to be searched :”

read s

l=0

c=0

u=$(($n-1))

while [ $l -le $u ]

do

mid=$(((( $l+$u ))/2 ))

if [ $s -eq ${a[$mid]} ]

then

c=1

break

elif [ $s -lt ${a[$mid]} ]

then

u=$(($mid-1))

else

l=$(($mid+1))

fi

done

if [ $c -eq 1 ]

then

echo “Element found at position $(($mid+1))”

else

echo “Element not found”

fi

OUTPUT

Enter the limit:  5

Enter the numbers

4 2 6 3 7

Sorted array is

2 3 4 6 7

Enter the number to be searched :7

Element found in position 5


LEAVE A REPLY