Thursday, September 13, 2012

Shift Reduce Parsing Technique


Parse the String ( a + b ) * c using Shift Reduce Parsing from the given grammar.
1.       E →(E)
2.       E →E+E
3.       E →E*E
4.       E →a | b | c
Answer:
Stack
Input
Operation
$
( a + b ) * c
Push (
$ (
a + b ) * c
Push a
$ ( a
+ b ) * c
Pop a & push E as E →a
$ ( E
+ b ) * c
Push +
$ ( E +
b ) * c
Push b
$ ( E + b
) * c
Pop b & push E as E →b
$ ( E + E
) * c
Pop E + E & push E as E →E + E
$ ( E
) * c
Push )
$ ( E )
* c
Pop ( E ) & push E as E → ( E )
$ E
* c
Push *
$ E *
c
Push c
$ E * c
$
Pop c & push E as E → c
$ E * E
$
Pop E * E & push E as E →E * E
$ E
$
Accept

Implementation in JAVA:
Compiler.java
import static java.lang.System.out;
import java.util.Scanner;
public class Compiler
{
    static Scanner s=new Scanner(System.in);
    public static void main(String args[])
    {
        out.print("How many Rule? :");
        int r=s.nextInt();
        String[][] rule=new String[r][2];
        out.println("Enter The Rule:");
        int i,j;
        for(i=0;i
        {
            for(j=0;j<2 j="j" p="p">
                rule[i][j]=s.next();
        }
        out.println("Rules are:");
        for(i=0;i
        {
            for(j=0;j<2 j="j" p="p">
            {
                out.print(rule[i][j]);
                if(j==0) out.print(" -> ");
            }
            out.println();
        }
        int choice;
        do
        {
        out.println("Enter the String:");
        String str=s.next();
        Stack stck=new Stack(str.length());
        for(j=0;j
        {
            out.println("PUSH : "+str.charAt(j));
            stck.push(str.charAt(j));
            out.println("top:"+stck.top);
       
        int isPush;
        do
        {
            isPush=0;
            String str2 = "";
        for(i=stck.top-1;i>=0;i--)
        {
            int pos=0;
            str2=new StringBuffer(str2).insert(pos, stck.stack[i]).toString();
            pos++;
            for(int k=0;k
            {
                out.println("Check Rule : String:"+str2);
                if(str2.equals(rule[k][1]))
                {
                    out.println("RULE MATCHED");
                    for(int pop=0;pop
                    {
                        out.println("POP : "+stck.pop());
                    }
                    stck.push(rule[k][0].charAt(0));
                    isPush=1;
                    out.println("PUSH : "+rule[k][0].charAt(0));
                }
            }
            for(int m=0;m
                out.print("\nStack: "+stck.stack[m]);
            out.println();
        }
        }while(isPush==1);
        }
        out.println("\nFINALLY IN THE STACK:");
        for(i=0;i
            out.print(stck.stack[i]);
       
        out.print("\nDo you want to check for another String(0-NO/1-YES)? ");
        choice=s.nextInt();
        if(choice==0) System.exit(0);
        }while(choice==1);
    }
}
Stack.java:

public class Stack
{
    public int top,size;
    public char stack[];
    Stack(int sizeOfStack)
    {
        this.size=sizeOfStack;
        stack=new char[size];
        top=0;
    }
    public boolean push(char x)
    {
        if(top==size) return false;
        else
        {
            stack[top++]=x;
            return true;
        }
    }
    public char pop()
    {
        if(top==0) return '0';
        else return stack[--top];
    }
    public boolean isEmpty()
    {
        if(top==0) return true;
        else return false;
    }
    public boolean isFull()
    {
        if(top==size) return true;
        else return false;
    }
}

OUTPUT:
How many Rule? :6
Enter The Rule:
E
a
E
b
E
c
E
E+E
E
E*E
E
(E)
Rules are:
E -> a
E -> b
E -> c
E -> E+E
E -> E*E
E -> (E)
Enter the String:
(a+b)*c
PUSH : (
top:1
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(

Stack: (
PUSH : a
top:2
Check Rule : String:a
RULE MATCHED
POP : a
PUSH : E
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a

Stack: (
Stack: E
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a

Stack: (
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: (
Stack: E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E

Stack: (
Stack: E
PUSH : +
top:3
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+

Stack: (
Stack: E
Stack: +
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+

Stack: (
Stack: E
Stack: +
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+

Stack: (
Stack: E
Stack: +
PUSH : b
top:4
Check Rule : String:b
Check Rule : String:b
RULE MATCHED
POP : b
PUSH : E
Check Rule : String:b
Check Rule : String:b
Check Rule : String:b
Check Rule : String:b

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E+E
Check Rule : String:E+E
Check Rule : String:E+E
Check Rule : String:E+E
RULE MATCHED
POP : E
POP : +
POP : E
PUSH : E
Check Rule : String:E+E
Check Rule : String:E+E

Stack: (
Stack: E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E

Stack: (
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: (
Stack: E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E

Stack: (
Stack: E
PUSH : )
top:3
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)

Stack: (
Stack: E
Stack: )
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)

Stack: (
Stack: E
Stack: )
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
RULE MATCHED
POP : )
POP : E
POP : (
PUSH : E

Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: E
PUSH : *
top:2
Check Rule : String:*
Check Rule : String:*
Check Rule : String:*
Check Rule : String:*
Check Rule : String:*
Check Rule : String:*

Stack: E
Stack: *
Check Rule : String:E*
Check Rule : String:E*
Check Rule : String:E*
Check Rule : String:E*
Check Rule : String:E*
Check Rule : String:E*

Stack: E
Stack: *
PUSH : c
top:3
Check Rule : String:c
Check Rule : String:c
Check Rule : String:c
RULE MATCHED
POP : c
PUSH : E
Check Rule : String:c
Check Rule : String:c
Check Rule : String:c

Stack: E
Stack: *
Stack: E
Check Rule : String:*c
Check Rule : String:*c
Check Rule : String:*c
Check Rule : String:*c
Check Rule : String:*c
Check Rule : String:*c

Stack: E
Stack: *
Stack: E
Check Rule : String:E*c
Check Rule : String:E*c
Check Rule : String:E*c
Check Rule : String:E*c
Check Rule : String:E*c
Check Rule : String:E*c

Stack: E
Stack: *
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: E
Stack: *
Stack: E
Check Rule : String:*E
Check Rule : String:*E
Check Rule : String:*E
Check Rule : String:*E
Check Rule : String:*E
Check Rule : String:*E

Stack: E
Stack: *
Stack: E
Check Rule : String:E*E
Check Rule : String:E*E
Check Rule : String:E*E
Check Rule : String:E*E
Check Rule : String:E*E
RULE MATCHED
POP : E
POP : *
POP : E
PUSH : E
Check Rule : String:E*E

Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: E

FINALLY IN THE STACK:
E
Do you want to check for another String(0-NO/1-YES)? 1
Enter the String:
(a+b)
PUSH : (
top:1
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(
Check Rule : String:(

Stack: (
PUSH : a
top:2
Check Rule : String:a
RULE MATCHED
POP : a
PUSH : E
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a
Check Rule : String:a

Stack: (
Stack: E
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a
Check Rule : String:(a

Stack: (
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: (
Stack: E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E

Stack: (
Stack: E
PUSH : +
top:3
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+
Check Rule : String:+

Stack: (
Stack: E
Stack: +
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+
Check Rule : String:E+

Stack: (
Stack: E
Stack: +
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+
Check Rule : String:(E+

Stack: (
Stack: E
Stack: +
PUSH : b
top:4
Check Rule : String:b
Check Rule : String:b
RULE MATCHED
POP : b
PUSH : E
Check Rule : String:b
Check Rule : String:b
Check Rule : String:b
Check Rule : String:b

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b
Check Rule : String:+b

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b
Check Rule : String:E+b

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b
Check Rule : String:(E+b

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E
Check Rule : String:+E

Stack: (
Stack: E
Stack: +
Stack: E
Check Rule : String:E+E
Check Rule : String:E+E
Check Rule : String:E+E
Check Rule : String:E+E
RULE MATCHED
POP : E
POP : +
POP : E
PUSH : E
Check Rule : String:E+E
Check Rule : String:E+E

Stack: (
Stack: E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E
Check Rule : String:(E+E

Stack: (
Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: (
Stack: E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E
Check Rule : String:(E

Stack: (
Stack: E
PUSH : )
top:3
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)
Check Rule : String:)

Stack: (
Stack: E
Stack: )
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)
Check Rule : String:E)

Stack: (
Stack: E
Stack: )
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
Check Rule : String:(E)
RULE MATCHED
POP : )
POP : E
POP : (
PUSH : E

Stack: E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E
Check Rule : String:E

Stack: E

FINALLY IN THE STACK:
E
Do you want to check for another String(0-NO/1-YES)? 0
BUILD SUCCESSFUL (total time: 48 seconds)


Posted by at No comments:

Wednesday, September 12, 2012

Stack


Algorithms of Stack:
Definition: A Stack is a linear data structure in which both insertion and deletion operations are performed only at one end. The end where insertion and deletion takes place is called the top of the stack or stack top.
·         A Stack also referred as Last in fast out (LIFO).
·         A Stack is an abstract data type that supports the following operations:
Operation
Description
isEmpty()
Check whether the stack is empty.
isFull()
Check whether the number of items in the stack is equal to the maximum allowable capacity of the stack.
push()
Store data items until stack full condition is reached.
pop()
Retrieve elements from the stack until the stack is empty.

Algorithms using Array:
   The simplest way to represent stack is by using one dimensional array, say stack[0 : SIZE-1], where SIZE is the maximum number of allowable entries. The first or bottom element in the stack is stored at stack[0], the second at stack[1], and the ith at stack[i-1]. Associated with the array is a variable, typically called top which points to the top element in the stack.   
Insertion Algorithm:
      Push an element onto the stack. Return true if successful; else return false. item is the element is to be pushed. Intially top is set to -1.

           Push( Stack, top, SIZE, item)
           {
                 if( top ≥ SIZE-1 ) then
                 {
                          write("Stack is full");
                          return false;
                  }
                  else
                  {
                         top := top+1;
                         stack[top] := item;
                         return true;
                   }

           }
Deletion Algorithm:
         Pop the top element from the stack. Return true if successful; else return false. item is used as output variable.
           Pop( Stack, top, SIZE, item)
           {
                 if( top < 0 ) then
                 {
                          write("Stack is Empty");
                          return false;
                  }
                  else
                  {
                         item := stack[top];
                         top := top-1;
                         return true;
                   }
           }
      Downloads:
             Program: Implementation in C
             Output:            
                Program: Implementation in c++ 
                Output:

         Program: Implementation in JAVA
Application Of Stack:
  1. Converting to infix expression to postfix expression.
  2. Converting to infix expression to prefix expression.
  3. Evaluation of postfix Expression.
  4. Evaluation of prefix Expression.

Posted by at No comments:

Tuesday, September 4, 2012

Analysis of BINARY SEARCH


BINARY SEARCH:
Let aᵢ, 1≤ i ≤n, be a list of Elements that are stored in non-decreasing order. Consider the problem of determining whether a given element x is present in the list. If x is present, we are determine a value j such that aj = x. If x is not in the list, then j is set to be zero. Let P= (n, ai, …., al) denote an arbitrary instance of this search problem (n is the number of elements in the list, ai, …., al is the list of elements, and x is the element for search for).
Divide-and-conquer can be used to solve this problem. Let Small(P) be true if n = 1. In this case S(P) will take the value i if x = ai ; Otherwise it will take the value 0.. Then g(1) = Θ(1). If P has more than one element, it can be divided into a new sub-problem as follows. Pick an index q in the range [i, l ] and compare x with aq. There are three possibilities:
1.       x = aq : In this case the problem P is immediately solved.
2.       x < aq : In this case x has to be searched for only the sub-list ai,ai-1,….,aq-1,x).
3.       x > aq : In this case sublist to be searched is aq+1,…..,al . P produces to ( l -q,aq+1,….,al,x).
In this example, any given problem P gets divided into one new sub-problem. This division takes only Θ(1) time. After a comparison with aq , the instance remaining to the solved (if any) can be solved by using this divide-and-conquer scheme again. If q is always chosen such that aq is the middle element (i.e. q = (n+1)/2), then the resulting search algorithm known as Binary Search. Note that the answer of the new sub-problem is also the answer of original problem P; There is no need for any combining.
Algorithm 1 describes this Binary Search method, where BinSearch has four input a[ ], i, l, and x. It is initially involved as BinSearch( a, 1, n, x).
·         Algorithm 1: Recursive Binary Search
BinSearch(a[], i, l, x)
// Give an array a[i:l] of elements in non-decreasing order,
// 1≤i≤l, determine whether x is present, and if so, return j
// such that x = a[j]; else return 0.
{
     if(l=i) then  // if Small(P)
     {
           if(x=a[i]) then return i;
           else return 0;
     }
     else
     {
     //Reduce P into smaller Sub-Problem.
           mid = (i+l)/2;
           if(x=a[mid]) then return mid;
           else if(x
           else return BinSearch(a,mid+1,l,x);
     }
}

                A non-recursive version of BinSearch is given in Algorithm 2. BinSearch has three inputs a, n, & x. The while loop continues processing as long as there more elements left to check. At the conclusion of procedure 0 is return if x is not present, or j is returned, such that a[j]=x.
                Is BinSearch an algorithm? We must be sure that all of the operations such as comparisons between x and a[mid] are well defined. The relational operator carry out the comparisons among elements of a correctly if these operators are appropriately defined.
                Does BinSearch Terminate? We observe that low & high are integer variable such that each time through the loop either x is found or low is increased by at least one or high is decreased by at least one. Thus we have to sequences of integers approaching each other and eventually low become greater than high and cause termination in a finite number of steps if x is not present.
·         Algorithm 2: Non-Recursive Binary Search
BinSearch(a, n, x)
// Give an array a[1:n] of elements in non-decreasing order, n≥0,
// determine whether x is present, and if so, return j such that
// x=a[j]; else return 0.
{
   low:=1; high:=n;
   while(low ≤ high)
   {
        mid:=(low+high)/2;
        if(x
        else if (x>a[mid]) then low:=mid+1;
        else return mid;
   }
return 0;
}
Example:
Let us consider 14 entries:
-15,-6,0,7,9,23,54,82,101,112,125,131,142,151
Place them in a[1:14] and simulate the steps that bin search goes through as it searches for different values of x. Only the variables low, high and mid need to be traced as we simulate the algorithm. We try the following values for x: 151,-14,9 for two successful searches and one unsuccessful search. The traces of these three inputs shows below:
X = 151          low         high       mid
                        1              14           7
                        8              14           11
12           14           13
14           14           14
                                Found

X = -14                  low         high       mid
                                1              14           7
                                1              6              3
                                1              2              1
                                2              2              2
                                2              1              Not Found

X = 9                      low         high       mid
                                1              14           7
                                1              6              3
                                4              6              5
                                                                Found
                To test all successful searches, x must take on the n values for a. To test all unsuccessful searches, x must take on the n+1 values for a. Thus complexity of BinSearch is 2n+1 for each n.
                Now Let analyze the execution profile of BinSearch. The two relevant characteristics of this profile are the frequency count and space required of the n elements of the array plus the variables low, high, mid and x, or n+4 locations. As for the time, there are three possibilities to consider: the best, average and worst cases.
                Suppose we begin determining the time for BinSearch on the previous data set. We observe that the only operations in the algorithm are comparisons and some arithmetic and data movements. We concentrate on comparisons between x and the elements in a[ ], recognizing that the frequency count of all other operations is of the same order as that for these comparisons. We assume that only one comparisons needed to determine which of the three possibilities of the if statement holds. The number of element comparison needed to find each of the 14 elements is
a:
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
Elements:
-15
-6
 0
7
9
23
54
82
101
112
125
131
142
151
Comparisons:
3
4
2
4
3
4
1
4
3
4
2
4
3
4

                No elements require more than 4 comparisons to be found. The average is obtained by summing the comparisons need to find all 14 items and dividing by 14. These yields 45/14, or approximately 3.21, comparisons per successful search on the average. There are 15 possible ways that an unsuccessful search may terminate depending on the value of x. If x
                The analysis just done applies to any stored sequence containing 14 elements. But the result we would prefer is a formula for n elements. A good way to derive such a formula plus a better way to understand the algorithm is to consider the sequence of values for mid that are produced by BinSearch for all possible values for x. These values are nicely described using a binary decision tree in which the value in each node is the value of mid. For example , if n=14, then below figure contain a binary decision tree that traces the way in which these values are produced by BinSearch.
             




The first comparison is x with a[7]. If xa[7], then the next comparison is a[11]. Each path through the tree represents a sequence of comparison in the binary search method. If x is present, then the algorithm will end at one of the circular nodes that lists the index into the array where x was found. If x is not present, the algorithm will terminate at one of the square nodes. Circular nodes are called internal node & square nodes are called external nodes.

Complexity:
                If n is in the range [2k-1,2k), that means 2k-1 ≤n <2 sup="sup">k
, then binary search makes at most k element comparisons for a successful search and either k-1 or k comparisons for an unsuccessful search. In other words the time for successful search is O(log n) and for Unsuccessful search is Θ(log n).
 Successful Search:
Best Case
Θ(1)
Average
Θ(log n)
Worst
Θ(log n)
               

                

Successful Search:
Best Case
Θ(log n)
Average
Θ(log n)
Worst
Θ(log n)





ADVANTAGES
1. In this method elements are eliminated by half each time .So it is very faster than the sequential search.
2. It requires less number of comparisons than sequential search to locate the search key element.
DISADVANTAGES
1. An insertion and deletion of a record requires many records in the existing table be physically moved in order to maintain the records in sequential order.
2. The ratio between insertion/deletion and search time is very high.


Implementation:
1.       Recursive Algorithm using C:

#include
#include
int BinSearch(int[],int,int,int);
void Sort(int[],int);

int main()
{
    int a[25],i=0,x,n,ch;
    printf("Enter Number of Elements:");
    scanf("%d",&n);
    printf("Enter Elements:\n");
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    Sort(a,n);
    printf("Given Elements:\n");
    for(i=1;i<=n;i++)
        printf("%d ",a[i]);
    do
    {
    printf("\nEnter Element to be Search:");
    scanf("%d",&x);
    if(BinSearch(a,1,n,x))
        printf("\nElement Found\n");
    else
        printf("\nElement Not Found\n");
    printf("Do you want to search again(0-NO/1-YES)? ");
    scanf("%d",&ch);
    if(ch==0) exit(0);
    }while(ch==1);
    return 0;
}
void Sort(int a[],int size)
{
    int i,j;
    for(i=1;i<=size;i++)
    {
        for(j=i+1;j<=size;j++)
        {
             if(a[i]>a[j])
             {
                 int t=a[i];
                 a[i]=a[j];
                 a[j]=t;
             }
         }
    }
}
int BinSearch(int a[],int i,int l,int x)
{
    int mid,flag=0;
    if(i==l)
    {
        if(x==a[i]) return i;
        else return 0;
    }
    else
    {
        mid=(i+l)/2;
        if(x==a[mid]) return mid;
        else if(x
        else return BinSearch(a,mid+1,l,x);
    }
}

Output:

2.       Recursive Algorithm using C++:

#include
#include
using namespace std;
class BinarySearch
{
    public:
    int BinSearch(int a[], int i,int l,int x);
    void Sort(int a[],int size);
};
void BinarySearch :: Sort(int a[],int size)
{
    for(int i=1;i<=size;i++)
    {
        for(int j=i+1;j<=size;j++)
        {
             if(a[i]>a[j])
             {
                 int t=a[i];
                 a[i]=a[j];
                 a[j]=t;
             }
         }
    }
}
int BinarySearch :: BinSearch(int a[],int i,int l,int x)
{
    int mid,flag=0;
    if(i==l)
    {
        if(x==a[i]) return i;
        else return 0;
    }
    else
    {
        mid=(i+l)/2;
        if(x==a[mid]) return mid;
        else if(x
        else return BinSearch(a,mid+1,l,x);
    }
}
int main()
{
    BinarySearch obj;
    int a[25],i=0,x,n,ch;
    cout<<"Enter Number of Elements:";
    cin>>n;
    cout<<"Enter Elements:"<
    for(i=1;i<=n;i++)
        cin>>a[i];
    do
    {
    obj.Sort(a,n);
    cout<<"Given Array:"<
    for(i=1;i<=n;i++)
        cout<
    cout<<"Enter Element to be Search:";
    cin>>x;
    if(obj.BinSearch(a,1,n,x))
        cout<<"\nElement Found";
    else
        cout<<"\nElement Not Found";
    cout<
    cout<<"Do you want to search again(0-NO/1-YES)? ";
    cin>>ch;
    }while(ch==1);
    return 0;
}

Output:

3.       Recursive Algorithm using JAVA:

import java.util.Scanner;
public class BinarySearch
{
                public static void main(String args[])
                {
                                Scanner s=new Scanner(System.in);
                System.out.print("Enter Number of Elements:");
                int n=s.nextInt();
                int i;
                int[] a=new int[n];
                System.out.println("Enter Elements:");
                for(i=0;i
                    a[i]=s.nextInt();
                                Sort(a);
                System.out.println("Given Elements:");
                for(i=0;i
                    System.out.print(a[i]+" ");
                System.out.println();
                int ch;
                do
                {
                System.out.print("Enter Element to be Search:");
                int t=s.nextInt();
                if(Search(a,0,a.length-1,t))
                    System.out.println("Element Found");
                else
                    System.out.println("Element Not Found");
                System.out.println("Do you want to Search again(0-NO/1-YES)? ");
                ch=s.nextInt();
                if(ch==0)
                    System.exit(0);
                }while(ch==1);
                }
        public static void Sort(int[] a)
        {
            for(int i=0;i
                {
                    for(int j=i+1;j
                    {
                        if(a[i]>a[j])
                        {
                            int t=a[i];
                            a[i]=a[j];
                            a[j]=t;
                        }
                    }
                }
        }
                public static boolean Search(int[] a,int low,int high,int t)
                {
                                int l,h,mid;
                                l=low;
                                h=high;
                if(t>a[h] || t
                    return false;
                                mid=(l+h)/2;
                                if(a[mid]==t)
                    return true;
                                else
                                {
                                                if(a[mid]
                                                                return Search(a,mid+1,h,t);
                                                else
                                                                return Search(a,0,mid-1,t);
                                }
                }
}

Output:

Posted by at No comments:
Subscribe to: Posts (Atom)