The main problem with k-nearest neighbor (k-NN) method is that the computational cost in the search process is proportional to the size of the training samples. Many search algorithms have been proposed to cope with this problem. In this study, we consider some conditions for terminating the search procedure when the true k-NNs have been found in the middle of the search, and we present, as an example, a procedure in the branch-and-bound algorithm. These conditions do not always work for a certain sample, but they reduce the computational cost on average.