Divide et Impera (Divide and Conquer)

"Divide et Impera" is the most important and most used technique to design efficient algorithms. Applied to solve a computational problem, this technique divides the problem into smaller and simpler subproblems, solves them, and then recombines partial solutions of the original problem.
The most famous algorithm that use it is the QuickSort.

Usually when you have to solve an algorithm with Divide et Impera you have to divide your array (or matrix) in 2 or more parts, choosing a pivot point (usually you can use the value that is in the middle of the array). Then you have to do a choice and decide if to do the recursive call on the left side of the array or on the right side.



A simple example (im using pseudocode):
Problem: We have an ordered array A[1...N]. We have to return true if the elements x is contained in the array, else return false.

We can solve this problem with a trivial algorithm.

findX (int A[], int x)
{
   int i;
   foreach i = 1 to N do
   {
        if (A[i] = x) {
              return true;
        } else {
        i++;
        }
    }
return false;
}

The complexity of this algorithm is O(n) because in the worst case we have to visit all the elements of the array. But we can solve this problem with a divide et impera algorithm which as complexity O(log n).

findX2 (int A[], int x, int first, last)
{
   int pivot = (i+j)/2;
   if (A[pivot] = x){
       return true;
   }
   else if (A[pivot] < x) {
      return findX2(A, x, first, pivot);
   }
   else {
     return findX2(A, x, pivot, last);
   }
}

As you can se we divide in 2 parts the array, and then we decide whether to go left or right. In this case we'll never visit all the elements, so we can consider findX2 better then findX.

R