C++ – Searching in array from both sides

In terms of Big-O time, no, since both methods are O(n).

In the first loop, you iterate less times but do more calculations per iteration. In the second loop, you do less calculations per iteration but do more iterations overall. I wouldn’t expect there to be any huge performance difference between the two, and the compiler might even change the two to be the same if you step through the assembly code.

It would also depend on the caching scheme your CPU is using, since in a large enough array the first loop may cache two blocks of memory rather than the second which would only cache one. This could have adverse effects on a direct-mapped cache, since the high and low indexes might refer to memory locations that occupy the same cache block, so accessing one after the other would result in constant cache misses.

At this point, it really is just up to what is more clear about what you are trying to accomplish, so I’d recommend loop #2. Not to mention, the second approach is far less error prone.

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top