This particular logic excersize, was, I think, one of the things that led Einstine to the Theory of General Relativity.
Case in point: any measure of half the distance can not be based on any constant in time, because there isn't any. We measure time more or less in terms of motion, weather it is counting out 1-mississippi 2-mississippi, using clockwork, quartz pulses, sand in a glass or cesium decay. It is all relative. We have an ideal of what we would like to measure, but just as with distance, there is no universal constant by which to judge it.
So the arrow is going to hit the target. The function of time is important to do conditions like drag, and trajectory. But both the target and the arrow (and the world they are in gravitational lock around) are in motion, so again there is no way to develop a contant which would lead to this paradox. It is only theoretical.