Questions regarding the binary search example

[rohanrayan]

Hi

Thanks for the book. Its very interesting.

I have one question regarding the binary search example that you have. The way you optimize further (after making it branchless and using prefetching) is to reorder it in an entzynger array. But since this is an O(n) operation anyway on the array, what is the point? We can as well search for the element while constructing the heap structure right? I dont see the need to do this and then do a binary search (albeit efficient) after that.

So to me it looks like you have introduced an additional O(n) operation to make the O(log n) operation faster, which doesnt make sense to me.