In this letter, a pilot structure and an efficient algorithm for downlink synchronization and cell searching in OFDM-based cellular systems are proposed. The pilots, randomly allocated in the frequency domain, allow us to minimize inter-cell interference (ICI) as well as to increase cell searching capability, estimation range of integer carrier frequency offset (CFO), and estimation accuracy of symbol timing offset (STO). The proposed low-complexity joint algorithm for integer CFO estimation, cell searching, and downlink detection is robust to ICI, multipath channel, STO and fine CFO.