A simplification error when calculating array lengths

Steven Schveighoffer schveiguy at yahoo.com
Mon Apr 7 05:51:45 PDT 2014


On Fri, 04 Apr 2014 18:30:28 -0400, Ali Çehreli <acehreli at yahoo.com> wrote:

> (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:
>
...

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, and  
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 = 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


More information about the Digitalmars-d-learn mailing list