Divide et Impera

What’s the difference between managing 5 people and managing 25 people? None (Surprise!). Group the people into 5 and pick a leader in each group. Each leader manages his/her group and you manage the 5 leaders.

This strategy is known as divide and conquer and has been used by many successful military leaders like Julius Ceasar who has been attributed the phrase “divide et impera” or Divide and Conquer. Not surprisingly, this is also used in programming.

Imagine you are asked to search a number in a sorted array of 1 million numbers. How will you search for it? A novice programmer will probably search for it one element at a time. The code would end up like this:


public int findNumber(int numToFind, int[] array){

  for( int i=0;i<1000000; i++){
    if(a[i] == numToFind)
       return i;
  }

  return -1;
}

What’s the worst case that can happen when searching for a number in a sorted array? When the number is the last number in the array or is not even in the array! When that happens, the number of times you traverse the “for loop” is 1 million! You can just imagine how long it takes for this algorithm to execute if you are now searching on an array of 1 trillion numbers.

However, if you make use of the fact that the array is sorted, something beautiful happens. You can search the array of 1 million numbers in less than 20 comparisons! The way to do it is to start searching at the middle. If x is the number you are searching, compare x with the middle element. If x is equal to it, then you’ve found your number. If not, then either x is greater than the middle element or less than the middle element. If you’ve found that x is less than the middle element, then obviously x is not in the right side of the array but can be on the left side. I say “can be” because x might not even be in the array. We can write this in a more structured manner

algorithm binarySearch( Array A): 
1. get the middle element A[middle]
2. compare x with A[middle]. If x equals A[middle] return middle.
3. if x less than A[middle], return binary search(A[1:middle-1]
4. else return binarySearch(A[middle + 1, n])

So how many times do we compare x to the middle element? How many comparisons are there in each iteration? Only one. Now it only remains to count the number of iterations for any sorted integer array of size n. To make things simpler, let us assume that n = 2^m, for some m (that is, n is a power of 2). At every iteration, we split the array size into two equal parts. The final iteration occurs when you have sufficiently divided the array so that there is only one element. So when does this happen? This happens when you have halved the array m number of times, or mathematically:

\displaystyle m = \log_2 n

Therefore, if you are given a sorted array of 1 million integers, the number of comparisons you need is only

\displaystyle \log_2 1000000 = 19.9

or about 20 comparisons. That’s amazingly fast!

Advertisements

Published by

Bobby Corpus

Is an IT Architect.

One thought on “Divide et Impera”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s