Divide and conquer in design and analysis of algorithm

Divide and conquer methods.

   The divide and conquer methods are used in designing algorithms when the function to be computed has n inputs.
   As the title of this methods indicates, the original problem of n inputs is divided, recursively by reapplication of the divide and conquer principle,
   into m subproblems for 1<=m<=n till it becomes easy to solve each of these m subproblems individually.
   
    The divide and conquer paradigm consists of the following three steps at each level of recursion.
      1. Divide the problem into a number of subproblems,
      2.Conquer the subproblems by solving them and 
      3. Combine the solutions of all the subproblems to obtain a solution for the original problem.

Binary Search:


We are given a sorted array a[1: n] of size n and a search element x. The problem is to determine whether x is present in the list a[] or not.If it is present
, we determine a value j such that a[j]=x, 1<=j<=n. If x is not present in the list, then proper action will be taken, maybe one can set conveniently, j=0.


The divide and conquer method is called a binary search method if m is chosen every time such that am is the middle element of the list, i.e., m=[(n+1)/2].


Now we represent recursive and iterative algorithms.

Algorithm 1. Recursive binary search.

1.Algorithm BinRSearch (a, j, x)
2.   //a[j, k] is a given sorted array of non-decreasing elements.
3.   //order, 1<=j<=k. This algorithm searches the list for the
4.   //presence of x. If the search is successful, i.e. if x is 
5.   //present, it returns i such that x=a[i], else returns zero.
6.    {
7.        if (k=j) then // small(P)
8.              {
9.                  if (x=a[j] ) then return j;
10.                     else return 0;
11.              }
12.                else
13.                {//p is divide into smaller subproblems.
14.               mid:=[(j+k)/2]
15.                     if ( x=a [mid]) then return mid;
16.                         else if ( x<a[mid]) then
17.                             return BinRSearch (a, j, mid-1,x);
18.                                else return BinRSearch (a, mid+1,k,x);
19.            }
20.       }



Algorithm 2. Iterative binary search

1.Algorithm ItBinsearch(a, n, x)
2. //a[1:n] is an array of n element in non decreasing
3.  //order. This algorithm determines whether x is present in
4. //a[] and if so returns i such that x =a[i ], else returns 0
5. {
6.   1:=1;h:=n;
7.   while (1 d'' hi ) do
8.              {
9.                  mid:=[(1+ h)/2];
10.                    if (x> a[mid]) then
11.                     h:=mid-1;
12.                    else if (x>a[mid]) then
13.                             1:=mid+1;
14.                           else return mid;
15.                }
16.           return 0;
17.   }




Algorithm3. Merge sort


1.Algorithm MergeSort (i,  j)
2.  // a[i, j] is an unsorted array.
3.   //small(p) is true if p can be solved directly.
4.   {
5.         if (i<j) then //s(p) is false
6.            {
7.            //Divide p into smaller sub problems 
8.          mid:=[(i+j)]
9.            MergeSort(i, mid);
10.           MergeSort (mid+1,j);
11.          //Combine the sub soultions
12.              Merge(i, j, mid);
13.           }
14.   }