Why is pointer arithmetic not working here?

Question

In the following program

#include <iostream>

bool contains ( int * sarr, size_t n, int i ) // checks whether the integer i is in the sorted array sarr of length n
{ 

    int * pa = sarr; int * pb = sarr + n;
    if (pa == pb) return false; // empty array
    --pb;
    while (pa != pb)
    {
        if (*pa == i || *pb == i) return true;
        int * pc = (pa + pb)/2;
        if (*pc < i)
            pa = pc;
        else 
            pb = pc;
    }
    if (*pa == i || *pb == i)
       return true;
    else 
       return false;
}


int main () 
{
    int arr [] = {1, 1, 6, 10, 19, 22, 22, 22, 50};
    std::cout << contains(arr, sizeof(arr)/sizeof(int), 6); // should print 1
    return 0;
}

I'm getting the compiler error

error: invalid operands of types 'int*' and 'int*' to binary 'operator+'

on the line

int * pc = (pa + pb)/2;

Why is that? I thought it was perfectly valid to add pointers. Or do I need to perform some casts on the right side?

How can I make that algorithm more compact and efficient while continuing to cover all the corner cases?

Also, I'm tagging this as both C and C++ because it's C-style C++.

You may want to look at http://stackoverflow.com/questions/394767/pointer-arithmetic — antron, May 24 '15 at 18:22

score 3 · Accepted Answer · answered May 24 '15 at 18:22

3

It is not valid to add pointers. It is valid to add integer values to pointers (offsets). You can work around that by using (pb - pa) / 2 + pa. Subtracting pointers gives you the size of the range.

answered May 24 '15 at 18:22

wilx

17,697
6
59
114

Can you divide pointers by integers? Could I do `(pa+(int)pb)/2`? – Microsoft Orange Badge May 24 '15 at 18:25
That is not valid. Divisions does not work on pointers. – wilx May 24 '15 at 18:28
@MicrosoftOrangeBadge I'd suspect no, what should the result represent actually? – πάντα ῥεῖ May 24 '15 at 18:29
So "pointer arithmetic" is limited to adding and subtracting integers from pointers? – Microsoft Orange Badge May 24 '15 at 18:30
Yes. Because pointers are not numbers. They are pointers. They may be advanced and the opposite, but that's it. – Lightness Races in Orbit May 24 '15 at 18:37

Why is pointer arithmetic not working here?

1 Answers1