Yes, multi-threaded access to the array would invalidate the assumptions made when designing that algorithm, as so often happens. And copying the array would c

Yes, multi-threaded access to the array would invalidate the assumptions made when designing that algorithm, as so often happens. And copying the array would cost more than you would save, so you would want to be sure that you don't have to do that. In general a growable array implementation will double the storage of the array (or multiply it by some other factor, such as the square root of 2) whenever it does grow it, so that it doesn't immediately have to grow it again. You could just arrange for your implementation to grow whenever there's only one storage location left, and then you could use this trick when searching it. But recall that this algorithm was designed in a context where neither of those constraints apply.