A voltage-controlled oscillator in a phase-locked loop circuit is calibrated via a dichotomous search in a set of candidate frequency bands via a sequence of subsequent halving steps that produce reduced subsets of the set of candidate frequency bands. The reduced subsets have respective upper bound values and lower bound values, as well as central values. The central value of the subset resulting from the halving step of index i in the sequence is a function of the average of the upper bound value and the lower bound value of the subset resulting from the halving step of index i−1 in the sequence.