• Welcome to Bashguru

    Linux is one of popular version of UNIX operating System. It is open source as its source code is freely available. It is free to use. Linux was designed considering UNIX compatibility. It's functionality list is quite similar to that of UNIX and become very popular over the last several years. Our Basic motive is to provide latest information about Linux Operating system.

  • Python Programming

    Python is a comparatively simple programming language, compared to c++. Although some of the benefits of c++ are abstracted away in python, they are replaced with an overall easier to learn language with many “intuitive” features. For this reason it is common and recommended by most professionals that people new to programming start with python.

  • Perl Programming

    Perl is an open-source, general-purpose interpreted programming language. Used often for CGI, Perl is also used for graphics programming, system administration, network programming, finance, bioinformatics, and other applications. The Perl languages borrow features from other programming languages including C, shell scripting (sh), AWK, and sed. They provide powerful text processing facilities without the arbitrary data-length limits of many contemporary UNIX command line tools, facilitating easy manipulation of text files.

  • Android

    Android is an operating system based on the Linux kernel, and designed primarily for touch screen mobile devices such as smart phones and tablet computers. Android is a Linux-based software system, and similar to Linux, is free and open source software. This means that other companies can use the Android operating developed by Google and use it in their mobile devices.Android gives you a world-class platform for creating apps and games for Android users everywhere, as well as an open marketplace for distributing to them instantly.

Monday, January 3, 2011

Posted by venu k
2 comments | 11:23 AM
 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

2 comments:

  1. Binary search [string pointer array]

    #include
    #include

    static int binsearch(char *str[], int max, char *value);

    int main(void) {
    /* note, array needs to be sorted for bsearch... */
    char *strings[] = { "bill", "chris", "jason", "randy", "trish" };
    int i, asize, result;

    i = asize = result = 0;

    asize = sizeof(strings) / sizeof(strings[0]);

    for(i = 0; i < asize; i++)
    printf("%d: %s\n", i, strings[i]);

    printf("\n");

    if((result = binsearch(strings, asize, "randy")) != 0)
    printf("`randy' found at position: %d\n", result);
    else
    printf("`randy' NOT found..\n");

    if((result = binsearch(strings, asize, "nick")) != 0)
    printf("`nick' found at %d\n", result);
    else
    printf("`nick' was NOT found..\n");

    return 0;
    }

    static int binsearch(char *str[], int max, char *value) {
    int position;
    int begin = 0;
    int end = max - 1;
    int cond = 0;

    while(begin <= end) {
    position = (begin + end) / 2;
    if((cond = strcmp(str[position], value)) == 0)
    return position;
    else if(cond < 0)
    begin = position + 1;
    else
    end = position - 1;
    }

    return 0;
    }

    ReplyDelete
  2. Scientist went on Moon with the help of moon education ,a country can make progress with the help of education ,we invent different technologies with the help of the best essay writing service education,education plays very important role in the development of a country ,it is important for every person.

    ReplyDelete