Showing posts with label binary search. Show all posts
Showing posts with label binary search. Show all posts

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 ;