what's the difference between mid=(beg+end)/2 and mid=beg+(end-beg)/2 in binary search?

10

1

It is a problem from C++ primer fifth edition problem 3.26, I don't know the difference between them ? May be the second one can avoid overflow.

Pegasus

Posted 2014-01-08T14:54:39.567

Reputation: 621

It even happened to the best: Jon Bentley's binary search in Programming Pearls contained that overflow bug. – TemplateRex – 2014-01-08T16:27:26.933

Possible duplicate of Why prefer start + (end - start) / 2 over (start + end) / 2 when calculating the middle of an array?

– Philipp Wendler – 2016-08-02T14:47:49.037

Answers

15

May be the second one can avoid overflow.

Exactly. There's no guarantee that beg+end is representable; but in the second case the intermediate values, as well as the expected result, are no larger than end, so there is no danger of overflow.

The second form can also be used for affine types like pointers and other random-access iterators, which can be subtracted to give a distance, but not added together.

Mike Seymour

Posted 2014-01-08T14:54:39.567

Reputation: 212 998

Amusingly, the space of pointers (and random access iterators) to a range is an affine space: so affine combinations of random access iterators (like taking their average) is a logically valid thing to do. We just lack affine combination primitives in C++. – Yakk - Adam Nevraumont – 2014-01-08T15:13:42.737

@Yakk: Thanks, I was wracking my brains to remember the word "affine". It's been too long since I studied pure maths. – Mike Seymour – 2014-01-08T15:25:15.723

It is a fine thing to remember. – Yakk - Adam Nevraumont – 2014-01-08T15:38:02.470

1

In general case the both expressions are invalid. For example the first expression is invalid because there is no such operation as + for pointers or iterators. The second expression is invalid in case when non-random access iterators are used. For example when bidirectional iterators are used.

So the correct construction in C++ will look the following way

mid = std::next( beg, std::distance( beg, end ) / 2 );

Vlad from Moscow

Posted 2014-01-08T14:54:39.567

Reputation: 1

When would you want to run a binary search on a non-random access iterator? – John Bartholomew – 2014-01-08T16:12:19.480

It is not only me. But the C++ Standard declares std::binary_search with forward iterators

template<class ForwardIterator, class T> bool binary_search(ForwardIterator first, ForwardIterator last, const T& value); – Vlad from Moscow – 2014-01-08T16:15:33.743

1I suppose it makes sense if the comparison function is very expensive. Usually it doesn't make sense though, since you lose the O(log n) bound on running time. – John Bartholomew – 2014-01-08T16:20:56.240

1

If we consider the two lines in a more generic setting, not related to binary search, the following observations can be made:

You are correct that the problem the second form tries to avoid is overflow, attempting to represent a number that is larger than the maximum representable number.

There is no restriction on how large the individual numbers beg and end are, so potentially they can both be larger than half of the maximum representable number. Adding them means that the intermediate result (beg+end) can overflow.

The second solution seems to eliminate the risk of overflowing, but introduces another one. If the values are signed values, their difference can again overflow (or underflow, depending on their signs). Unsigned values have no problem.

There is another solution which you didn't post:

mid = beg/2 + end/2

This solves every problem with overflow and underflow, but introduces a new problem, of precision loss. If working with integer values, division by 2 can give a result off by 0.5, adding these together, means that mid can be off by 1:

mid = 3/2 + 5/2; // mid is 3, instead of the 4 expected

Working with floating point values has other precision problems.

Getting back to the problem at hand, the binary search, it's easy to see that beg and end are unsigned values, so the second solution will always give the correct result.

Tibos

Posted 2014-01-08T14:54:39.567

Reputation: 23 040

1

The answer is in the book:

"Because the iterator returned from end does not denote an element, it may not be incremented or dereferenced."

Graphically it makes sense as an asymmetric range, [begin, off-the-end) or half-open range.

From Accelerated C++, page 28, Koenig.

Lee

Posted 2014-01-08T14:54:39.567

Reputation: 16