-->

Saturday, March 22, 2014

The algorithms using recursion Ascending and Descending order array

The algorithms using recursion Ascending and Descending order array

We can rewrite both the algorithms using recursion:

Ascending order array:

BINSEARCH(arr, FIRST, LAST, key)
[‘arr’ is one-dimensional array of size ‘n’, key is element to search ]
[‘arr’ elements are stored in ascending order]
[FIRST is lower bound and LAST is upper bound of the array]
MID <--INTEGER((FIRST+LAST)/2)
If (arr[MID] = key) Then:
 Return 1[1for TRUE, successful search]
Else:
   If FIRST > LAST Then:
     BINSEARCH(arr, FIRST, MID-1, key)
    Else:
      BINSEARCH(arr, FIRST, MID+1, LAST,  key)
     [End of If]
  [End of If]
[End of if]
Exit.

Descending order array:

BINSEARCH(arr, FIRST, LAST, key)
[‘arr’ elements are stored in descending order]
[FIRST is lower bound and LAST is upper bound of the array]
MID <-- INTEGER((FIRST+LAST)/2)
If(arr[MID]= key) Then:
  Return 1[1 for TRUE, successful search]
Else:
  If FIRST>LAST Then:
    Return 0[0 for FALSE, unsuccessful search]
  Else:
     If arr[mid] > key Then:
        BINSEARCH(arr, MID+1,LAST,key)
      Else:
        BINSEARCH(arr, FIRST, MID+1, key)
       [End of If]
   [End of If]
[End of If]
Exit.
 

Read other related articles

Also read other articles

© Copyright 2013 Computer Programming | All Right Reserved