CODEWITHSUNDEEP
algorithmbinary-search
the_kshitij
the_kshitij

Reputation: 41

The effect of using mid=first+(last-first)/2 instead of (first+last)/2

Why do people use mid=first+(last-first)/2 instead of (first+last)/2,in case of binary search) Is there a difference between the two. If there is then please tell as I can't understand the difference.

Upvotes: 2

Views: 754

Answers (4)

M.Moustafa
M.Moustafa

Reputation: 31

both will give the same result if first+last < Maximum_value_for_a_variable. so it is much safer using mid=first+(last-first)/2 to avoid overflow. let's assume first, last and mid are int variables.

int mid; 
int first = 50010;
int last = 2147483275;
//Maximum value for a variable of type int is 2147483647
(first+last)/2 //-1073717005 overflow because first+last > integer maximum value
first+(last-first)/2 //1073766642 no overflow

Upvotes: 1

Reetesh Kumar
Reetesh Kumar

Reputation: 289

In most of the programming languages, there's a limit for a data type. So, if we use (first+last)/2 then adding first and last might exceed that given limit and it will produce a run time error.

To avoid this, it is advised to use first + (last-first)/2. As in extreme scenarios also, it will not cross the limit of its data type.

Upvotes: 0

Emma
Emma

Reputation: 27723

Yes, in Java and C++ for instance the latter ((hi + lo) / 2) might throw an exception, if hi + lo becomes too large. In Python and JavaScript, it would probably be okay.

It seems there are more info about that here.

Reference

Calculating mid in binary search

Upvotes: 1

thisisjaymehta
thisisjaymehta

Reputation: 643

If you use mid = (first + last) / 2 then there is a chance of overflow when first or last is MAX, i.e. when first or last is the maximum or range, adding one more number to it will overflow.

So we use mid = first + (last-first) / 2, as this will not overflow even when first or last is the max of range.

Also, as in competitive programming test cases are made which will test your code to extreme scenarios, it is very much possible that one of the test case has these maximum of range number. So it advisable to use mid = first + (last-first)/2

Upvotes: 4

Related Questions