Swift and accurate alignment of transmitter (Tx) and receiver (Rx) beams is one of the fundamental design challenges to support directional transmission in millimeter-wave cellular communications. In this paper, we propose a new Optimized Two-Stage Search (OTSS) algorithm for Tx-Rx beam alignment via beam training. In contrast to one-shot exhaustive search, OTSS judiciously divides the training energy budget into two stages. In the first stage, OTSS explores and trains all candidate Tx-Rx beam pairs and then discards a set of less favorable pairs learned from the measured received signal. In the second stage, OTSS takes an extra measurement for each of the remaining pairs and combines with the previous measurement to determine the best one. For OTSS, we derive fundamental bounds on its misalignment probability under a single-path channel model with ideal codebooks and establish a guideline on its optimized parameter choices. Numerical results have confirmed the advantage of OTSS over the state-of-the-art baselines.