Arithmetic operation in pointer using C

[shanmugarajaa]

Hi friends, I tried out something like this which is given below in VC++ by referring Dennis M. Ritchie (ANSI C second edition) book examples. struct Key *low = &tab[0]; struct Key *high = &tab[n]; struct Key *mid; mid = low + (high-low) / 2; // Error: cannot convert from 'int' to 'struct Key *' My question is how they are using this expression mid = low + (high-low) / 2;?. I don't know whether I misunderstood the concept or there is some difference between ANSI C and VC++. Please anyone help me in this. Regards, S.Shanmuga Raja

[Lost User]

Which compiler gives the error? I just tried this with Visual Studio 2010 C++ compiler and it compiles correctly, as it should, in both .c and .cpp versions.

Veni, vidi, abiit domum

[Bill_Hallahan]

There is a difference between ANSI C, some other C++ compilers, and what Visual Studio allows for pointer arithmetic. Pointer arithmetic is not allowed on all platforms, as least not allowed the way you have it. There is a ptrdiff_t macro that allows taking pointer differences on many platforms, but I'm not sure whether that is allowed in ANSI C or not. In any event, that is not what you need. Some compilers will let you cast a pointer to be type size_t, however, that is not portable across all platforms and compilers and is generally not a good practice. Presumably, the array tab is defined to be an array of Key structures: So, to write portable code, write code something like this:

int BinarySearch(int low, int high, struct Key x)
{
int index = -1;
int mid = 0;

while (low <= high)
{
    mid = (low + high) >> 1;

    if (firstKeyLessThanSecondKey(x, tab\[mid\]))
    {
        high = mid - 1;
    }
    else if (firstKeyLessThanSecondKey(tab\[mid\], x))
    {
        low = mid + 1;
    }
    else
    {
        index = mid;
    }
}

return index;

}

To search the entire tab array for a Key equal to x, pass 0 for low and the array length minus 1 for high. This will return -1 if the Key that matches x is not found, otherwise the index into the array tab for the key that matches x will be returned. Because the values of low and high are always positive, a shift can be used for the divide by 2.

    mid = (low + high) >> 1;

Of course, you'll have to modify this code for your application. I made some assumptions based on the book you cited. Also, if the Key structure isn't very small, then instead of passing the Key structure by value, you might want to pass a pointer to a Key to both the BinarySearch function and to the FirstKeyLessThanSecondKey function. Finally, I didn't compile and test this. I'm never 100% sure if code is correct until I debug it under varied conditions. If not correct, I expect this is very close to correct.