Tumor suppressor p53 slides along DNA and finds its target sequence in drastically different and changing cellular conditions. To elucidate how p53 maintains efficient target search at different concentrations of divalent cations such as Ca2+ and Mg2+, we prepared two mutants of p53, each possessing one of its two DNA-binding domains, the CoreTet mutant having the structured core domain plus the tetramerization (Tet) domain, and the TetCT mutant having Tet plus the disordered C-terminal domain. We investigated their equilibrium and kinetic dissociation from DNA and search dynamics along DNA at various [Mg2+]. Although binding of CoreTet to DNA becomes markedly weaker at higher [Mg2+], binding of TetCT depends slightly on [Mg2+]. Single-molecule fluorescence measurements revealed that the one-dimensional diffusion of CoreTet along DNA consists of fast and slow search modes, the ratio of which depends strongly on [Mg2+]. In contrast, diffusion of TetCT consisted of only the fast mode. The disordered C-terminal domain can associate with DNA irrespective of [Mg2+], and can maintain an equilibrium balance of the two search modes and the p53 search distance. These results suggest that p53 modulates the quaternary structure of the complex between p53 and DNA under different [Mg2+] and that it maintains the target search along DNA.