Tuesday, April 01, 2008

Divide and Conquer algorithms, trick

Possible mistake in implementing Divide and Conquer algorithms is, In many cases you may need to divide the input range.

Take Binary search as an example:
in each step we need to calculate "mid".

//Common practice of doing this:
// Broke - if (start + end) > Integer.MAX_VALUE
// Mid value will be assigned with -ve value.

mid = (start + end) / 2;                                                      

// Better way to avoid the problem
mid = start + (end - start)/2 ;

2 comments:

Anonymous said...

Supereb

amadamala said...

@praveen, Thanks,

I forgot mentioned that, it is discovered by java guru Joshua Bloch[author of Effective java]

Go through this link ....
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html