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

- =?UTF-8?B?QWxpIMOHZWhyZWxp?= (36/36) Apr 04 2014 (This was in C and probably a common mistake that I haven't experienced
- Steven Schveighoffer (21/28) Apr 07 2014 ...

(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