To create the count OR to create the array of indices, each element needs to be inspected one way or another, the array just needs another allocation, but we already know the worst case upper size limit. The count is not that inexpensive, IMHO. In one of your versions above, you are creating a full-size allocations for the boolean array, just to throw it away nanoseconds later and you are visiting each element of big arrays twice, first to create the boolean array and then again in the FOR loop.
Of course we don't know what the compiler does in the final machine code. 😉 Any "count" output would need to be smart enough not to generate any code unless the output is actually wired. Imagine we use "search array" in a loop and with each iteration the count is also generated. This would turn into ~O(N²). Not very cheap.
I still feel that "search array" should not be burdened with another output
>In one of your versions above, you are creating a full-size allocations for the boolean array, just to throw it away nanoseconds later and you are visiting each element of big arrays twice, first to create the boolean array and then again in the FOR loop.
The point is that that is removed by the compiler when it's not used.
I do know that, as the timing exactly matches the version where it isn't there at all.
