3 ms·

I think the reframing of the problem does make it look easier at first, but then you end up needing those three special cases which in my opinion negates the el

• hddqsb 5y ago
  The three special cases are unnecessary (see my top-level comment). Implementations that terminate early might seem faster at fist glance, but they can actually be slower: they only save 1 iteration on average*, and they require up to 2 branches in each iteration instead of 1. The cost of doubling the number of branches can outweigh the savings (1 iteration out of log2(n)). A possible exception is if the comparison function is expensive and returns a rich comparison (less/equal/greater), in which case it might make sense to perform the 2 branches. But a much more significant disadvantage of terminating early is that when the target element appears multiple times, there is no guarantee which occurrence will be found. *Incomplete proof that the saving is only 1 iteration on average: n/2 cases will not terminate early, n/4 will terminate 1 iteration early, n/8 will terminate 2 iterations early, n/16 will terminate 3 iterations early, etc. So the total saving is n/4*1 + n/8*2 + n/16*3 + ... which is at most n (the proof is the same as for the time complexity of the "heapify" operation).