to find the middle item in a vector, why use "mid = beg + (end - beg) / 2" instead of " mid = (beg + end) /2"

Question

I'm new to C++. I saw this code online, where it is trying to find a string within a vector. However, I have noticed right towards the end:

mid = beg + (end - beg) / 2;

Why does it have to be written in this way, why can't it be written as:

mid = (beg + end) /2

Is mid = (beg + (end - 1)) / 2 a feasible alternative?

I'm struggling to understand the reason behind it.

vector<string> text = {"apple", "beer", "cat", "dog"};
    string sought = "beer";

    auto beg = text.begin(), end = text.end();
    auto mid = text.begin() + (end - beg) / 2;
    while (mid != end && *mid != sought){
        if(sought < *mid){
            end = mid;
        } else {
            beg = mid + 1;
        }
        mid = beg + (end - beg) / 2;
    }

For one, the other one won't compile. Neither will the alternative. What does it mean to add two iterators? — chris, Feb 16 '16 at 01:49
yes, i tried the alternative and it wouldnt compile. But I'm struggling to understand the reason behind it. Could you kindly explain it to me? Thanks — Thor, Feb 16 '16 at 01:49
The beg variable is only at the beginning of the vector the first time. After that, you're moving either the near end or the far end to the old mid-point so as to reduce the search space. This method is called a binary search because it reduces the search space by 1/2 each iteration (it's a O(logn) algorithm) — P. Hinker, Feb 16 '16 at 01:57
@dzjustinli: The difference between two random access iterators results in the number of elements between the two. Adding two iterators doesn't make sense, so that operation isn't provided for iterators. However, adding a number (which presumably would represent a number of elements) does make sense, so addition of a number to an iterator is provided. Your proposal adds two iterators so it doesn't compile. — Michael Burr, Feb 16 '16 at 02:13
Possible duplicate of [Why we write lo+(hi-lo)/2 in binary search?](http://stackoverflow.com/questions/25571359/why-we-write-lohi-lo-2-in-binary-search) — phuclv, Feb 16 '16 at 02:44

Vaughn Cato · Accepted Answer · 2016-02-16T02:01:21.423

In general with binary search, the reason is to avoid overflow. beg+end is subject to overflow with large values. Using end-beg avoids the overflow.

Imagine of beg was MAX_INT-3 and end was MAX_INT-1, then beg+end would be larger than MAX_INT, but end-beg, would just be 2.

With iterators, this also works out because end-begin is a number, whereas begin+end is not valid. You can subtract two iterators to get the distance between them, but you can't add two iterators.

songyuanyao · Answer 2 · 2016-02-16T09:35:42.440

Adding two iterators doesn't make sense, and you can't do that.

You can call operator- on two iterators, and gives a reasonable result, i.e. the count of elements between two iterators. And you can add or subtract an integral number on iterator, means move it forward or backward. But what should be the result of adding two iterators?

mid = beg + (end - beg) / 2;
             ~~~~~~~~~~      => get the count between beg and end
            ~~~~~~~~~~~~~~~  => get the half of the count
      ~~~~~~~~~~~~~~~~~~~~~  => get the iterator pointing to the middle position between beg and end

mid = (beg + end) /2
       ~~~~~~~~~  => What would the result represent?

to find the middle item in a vector, why use "mid = beg + (end - beg) / 2" instead of " mid = (beg + end) /2"

2 Answers2