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 ;
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:
Supereb
@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
Post a Comment