Computing an integral basis for $ Q (\theta) $, $ \theta $ a root of an irreducible cubic

Question

To compute an integral basis in this case, we want to calculate $ \Delta (1, \theta, \theta^2) $, see if there are any primes dividing this number, and, if there are, consider the combinations $ \displaystyle \frac{u_0 + u_1 \theta + u_2 \theta^2}{p} $, where the $ u_i $ are natural numbers strictly less than $ p $. If one of these is an algebraic integer, we make $ \displaystyle 1, \theta, \frac{u_0 + u_1 \theta + u_2 \theta^2}{p} $ our new basis (edit: well, actually, I guess this depends on which coefficients are zero - this wouldn't be a basis if $ u_2 $ equaled $ 0 $, so we'd instead have to replace either $ 1 $ or $ \theta $ - to be honest I don't fully understand why this works) then, I think, we repeat until we get a basis whose discriminant is divisible by no prime. The issue I have is what do you do when your discriminant is divisible by a prime and none of the solutions $ (u_0, u_1, u_2) $ yield algebraic integers? I've looked it up on here before and some people say, for instance if p = 2, that the ring of algebraic integers would then just be $ \frac{1}{2} \mathbb{Z} (\theta) $. But isn't this akin to saying that $ (1,1,1) $ is a solution, which we know it isn't? My intuition says that, if there are no such solutions, then our original choice of basis $ 1, \theta, \theta^2 $ already is an integral basis.