4 ms·
It's already questionable for a search algorithm to require the ability to write to the array it's searching in, but it's even worse if it wants to be able to e
by Arnavion 7y ago
It's already questionable for a search algorithm to require the ability to write to the array it's searching in, but it's even worse if it wants to be able to extend and shrink the array to do so.
Edit: I haven't read the book. Presumably it gives some context for the algorithm that you only bring it out in the specific situation where it makes sense to use it.
- renox 7y agoExtending the array is not needed: you can store the last element in a variable, then overwrite the last element with the searched value, do the search then restore the last element. I remember a talk from Alexei Andrulescu(sp?) where he talk about this optimisation but I don't remember if there was benchmarks.
- mkl 7y agoThat's clever, but it still requires writing to the array, which is dodgy in many circumstances; other threads may be using it, so the search function is likely to be given only read-only access.