This paper investigates the secure state estimation problem of cyber-physical systems (CPSs) under sparse sensor attacks. First, a novel algorithm, which uses a switched gradient descent technique to harness the intrinsic combinatorial complexity of the secure state estimation problem, is proposed to estimate the state. The computational complexity is reduced through improving the convergence rate, reducing the number of candidates to be searched, reducing the search times, and reducing the computing resources consumed by each incorrect candidate selection simultaneously. Second, based on the proposed switched gradient descent algorithm, an observer-based algorithm is proposed to efficiently update the state estimation while new measurements are available. Compared with the existing methods, the computational complexity is reduced greatly without introducing any constraint except the basic observability assumption by adopting the proposed algorithms. (C) 2019 Elsevier Ltd. All rights reserved.