Millimeter-wave communications rely on narrow-beam transmissions to cope with the strong signal attenuation at these frequencies, thus demanding precise alignment between transmitter and receiver. The beam-alignment procedure may create a significant overhead, thus potentially offsetting the benefits of using narrow communication beams. In this paper, an optimal interactive energy-efficient beam-alignment protocol is designed, that optimizes over the sequence of beams and the duration of beam-alignment, based on feedback received from the user-end (thus, interactive), so as to support a minimum communication rate. It is proved that a fixed-length fractional search method that decouples the beam-alignment of base-station and user-end is optimal. Numerical results using analog beams demonstrate the superior performance of our proposed fractional search: the conventional and interactive exhaustive search methods, and the bisection search method incur, respectively, 7. 5dB, 14dB and 4dB of additional power consumption compared to the proposed fractional search.