Of course the array construction won't add to the time if you don't include it in the code that's timed.

You assume the same list is always searched.

I suppose a more precise analysis is O(log(N) + N/M) where M is the number of searched performed between modifications of the list. The number of such searches have to be proportional to the size of the list to get less than O(N).