A key challenge for starshades is formation flying. To successfully image exoplanets, the telescope boresight and starshade must be aligned to ~1 m at separations of tens of thousands of kilometers. This challenge has two parts: first, the relative position of the starshade with respect to the telescope must be sensed; and second, sensor measurements must be combined with a control law to keep the two spacecraft aligned in the presence of gravitational and other disturbances. In this work, we present an optical sensing approach using a pupil imaging camera in a 2.4-m telescope that can measure the relative spacecraft bearing to a few centimeters in 1 s, much faster than any relevant dynamical disturbances. A companion paper will describe how this sensor can be combined with a control law to keep the two spacecraft aligned with minimal interruptions to science observations.