In this article, we have explained the challenges and problems while finding the middle element, proposed solutions like David's method, Howard's version and how std::midpoint in C++ solves the problem.

Table of contents:

1. Problems & Challenges with middle element
2. Davis's method for mid point
3. Howard's version for mid point
4. Perfect method for mid point
5. How to use std::midpoint in C++?

Let us get started with std::midpoint in C++.

Problems & Challenges with middle element

Before starting this topic first we need to answer this question:

Whats wrong with a+b/2 ?

As per The CppCon 2019: Marshall Clow “std::midpoint? How Hard Could it Be?”.This method of calculating midpoint is prone to error.

Why?

It's because it induces the overflow. It has let many languages suffer from Java to Javascript rendering the whole world at risk.

But! It seems fine for any digit.

Yes it may be fine for any digit but it cannot be used for other types like float, int32_t and any other types.

Implementation on these genrates wrong outputs that are unexpected and unwanted. So for this various ways were proposed one of which were

a + (b-a) / 2

But this was also rejected due to overflow issues. Then came another way to handle this issue which was mentioned in Davis' original Paper(R0/R1/R2).

Davis's method for mid point

using U = std::make_unsigned_t<Integer>;
return Integer( U(a) + ( U(b) - U(a) )/2 );

But the paper failed due unhandled exception.

midpoint(1,6) = 3
midpoint(6,1) = -2147483645

The revised paper attended the logic more subtly by

using U = std::make_unsigned_t<Integer>;
return a>b ? a - (U(a)-b)/2 : a + (U(b)-a)/2;

But it still had many shortcomings as it failed again in tests

midpoint(1,6) = 3
midpoint(6,1) = 4
short a = -3
short b = -4
midpoint(a,b) = 32765
midpoint(b,a) = 32764

So came now what we have as Howard's version.

Howard's version for mid point

Using U = std:: make_unsigned_t<Integer>;
int sign = -1;
U m = a; U M = b;
if(a>b){
    sign = -1;
    m=b;
    M=a;
  }
return a + sign * Integer((M-m)/2);

But this method is also prone to errors. It genrates errors too.

  short a = -3
  short b = -4
  midpoint(a,b)=-3
  midpoint(b,a)=-4
  short c = 4
  midpoint(a,c)=-127
  midpoint(c,a)=-128

Perfect method for mid point

Now finally to counter it we need to revise the code so that it can deal with these error

Using U = std:: make_unsigned_t<Integer>;
int sign = -1;
U m = a; U M = b;
if(a>b){
    sign = -1;
    m=b;
    M=a;
  }
return a + sign * Integer(U(M-m)>>1);

The change here was wrapping the answer as U type and using right shift instead of simple division which provides more smooth calculation for computer.

Thus we use std::midpoint to get the most advanced method.

Flavours to std::midpoint

• Integral Types
• Pointers
• Floating Point Types

How to use std::midpoint in C++?

For implementing this function we will use header file

<numeric>

And we will use the function as

midpoint( dataTypeA , dataTypeB )

Code to implement

#include <iostream>
#include <numeric>
using namespace std;

int main()
{
        int a = 5;
        int b = 7;
        float c = 4.5;
        float d = 5.5;
        char text[] = "PointerMidpoint";
    
        cout << "midpoint(" << a<< ", " << b << "): "<< midpoint(a, b) << endl;
        cout << "midpoint(" << c<< ", " << d << "): "<< midpoint(c, d) << endl;
        cout << "midpoint(" << text[2] << ", " << text[6] << "): "<< midpoint(c, d) << endl;
        

	return 0;
}

Output

midpoint(5,7):6
midpoint(4.5,5.5):5.0
midpoint(i,r):t

With this article at OpenGenus, you must have the complete idea of using std::midpoint in C++.