## digitalmars.D.learn - A simplification error when calculating array lengths

```(This was in C and probably a common mistake that I haven't experienced
until today.)

tldr; The following two expressions are not equivalent:

a)    length - 1 - length / 2
b)    length / 2 - 1

I was trying to write a recursive function similar to binary search:

- Process the middle element

- Call the same function with the left half

- Call the same function with the right half

void foo(int * arr, size_t length)
{
if (!length) {
return;
}

// Process the middle element
process(arr[length / 2]);

// Handle the left side
foo(arr, length / 2);

// Handle the right side (+1 to skip the middle element)
foo(arr + length / 2 + 1, /* ??? */);
}

What should be the length of the right half on the last line? Minus 1
for the already-processed middle element and minus length/2 for the left
half:

a)    length - 1 - length / 2

That seems to be correct. Then I simplified:

b)    length / 2 - 1

And that was a mistake because b produces size_t.max when length==1 to
begin with. So, the calculations a and b are not equivalent. You knew it
already ;) but it surprised me today.

Also, this is not an issue with D's slices because slices remove the
need for such calculations:

foo(arr[\$ / 2 + 1 .. \$]);    // Simple and correct

Which also means that maybe I should have used a pair of pointers in the
original function instead of a pointer and a length.

Ali
```
Apr 04 2014
```On Fri, 04 Apr 2014 18:30:28 -0400, Ali =C3=87ehreli <acehreli yahoo.com=
wrote:

(This was in C and probably a common mistake that I haven't experience=

d  =

until today.)

tldr; The following two expressions are not equivalent:

a)    length - 1 - length / 2
b)    length / 2 - 1

I was trying to write a recursive function similar to binary search:

...

I have implemented binary search many many times. Almost EVERY time,  =

things like this get me. Generally, it ends up getting stuck in an  =

infinite loop in some corner cases. It's one of those things where it  =

seems so simple in concept, but ends up being so tricky to implement, an=
d  =

even harder to test.

I think your idea of using pointers is a good one.

But another rule of thumb I like to follow -- try not to be too clever  =

when dealing with tricky code :) Brevity does not always equal quality:

unsigned int midpoint =3D length / 2;
// Process the middle element
process(arr[midpoint]);

// Handle the left side
foo(arr, midpoint);

// Handle the right side
++midpoint;
foo(arr + midpoint, length - midpoint);

-Steve
```
Apr 07 2014