It is basically the same problem as when some guys attempt to divide some public key by 2, 4, 8 etc.
Every time we "divide" we cannot tell if the resulting point lies in the lower half of the interval, or whether it is offset by (groupOrder + 1)/2, because we don't know the parity of the private key.
Regarding this very specific problem, one limited approach I can think of is to subtract G from your initial pubkey and keep them both; the initial and the offset resulting from this subtraction.
Now one of these two is sure to have an even private key, as some pubkey minus G = its private key minus 0x1.
Then you "divide" them both and at least one resulting offset will be within the desired interval.
Idk if this would be a feasible approach for your original problem tho, as the "decision tree" grows exponentially every time we repeat this process.