Protein search for targets on DNA starts all major biological processes. Although significant experimental and theoretical efforts have been devoted to investigation of these phenomena, mechanisms of protein-DNA interactions during the search remain not fully understood. One of the most surprising observations is known as a speed-selectivity paradox. It suggests that experimentally observed fast findings of targets require smooth protein-DNA binding potentials, while the stability of the specific protein-DNA complex imposes a large energy gap which should significantly slow down the protein molecule. We developed a discrete-state stochastic approach that allowed us to investigate explicitly target search phenomena and to analyze the speed-selectivity paradox. A general dynamic phase diagram for different search regimes is constructed. The effect of the target position on search dynamics is investigated. Using experimentally observed parameters, it is found that slow protein diffusion on DNA does not lead to an increase in the search times. Thus, our theory resolves the speed-selectivity paradox by arguing that it does not exist. It is just an artifact of using approximate continuum theoretical models for analyzing protein search in the region of the parameter space beyond the range of validity of these models. In addition, the presented method, for the first time, provides an explanation for fast target search at the level of single protein molecules. Our theoretical predictions agree with all available experimental observations, and extensive Monte Carlo computer simulations are performed to support analytical calculations.