2d - What's the most efficient way to find the intersection point of a missile and a bitmap terrain?

Following up on my earlier question about finding the slope of a 2D bitmap terrain I now need to know the best way of finding the point on the 2D terrain that the missile hit. Obviously, I can see if any pixels under the missile intersect terrain, but say it has moved quite deep into the terrain.

What is the best way to step back to find where it initially collided? I could move back X pixels at a time towards the missile's previous position, but what would be a good value of X? And is there a smarter way? Maybe moving half the distance, then a quarter etc?