The steered response power-phase transform (SRP-PHAT) sound source localization algorithm is robust in a real environment. However, the large computation complexity limits the practical application of SRP-PHAT. For a microphone array, each location corresponds to a set of time differences of arrival (TDOAs), and this paper collects them into a TDOA vector. Since the TDOA vectors in the adjacent regions are similar, we present a fast algorithm based on clustering search to reduce the computation complexity of SRP-PHAT. In the training stage, the K-means or Iterative Self-Organizing Data Analysis Technique (ISODATA) clustering algorithm is used to find the centroid in each cluster with similar TDOA vectors. In the procedure of sound localization, the optimal cluster is found by comparing the steered response powers (SRPs) of all centroids. The SRPs of all candidate locations in the optimal cluster are compared to localize the sound source. Experiments both in simulation environments and real environments have been performed to compare the localization accuracy and computational load of the proposed method with those of the conventional SRP-PHAT algorithm. The results show that the proposed method is able to reduce the computational load drastically and maintains almost the same localization accuracy and robustness as those of the conventional SRP-PHAT algorithm. The difference in localization performance brought by different clustering algorithms used in the training stage is trivial. The steered response power-phase transform (SRP-PHAT) sound source localization algorithm is robust in a real environment. However, the large computation complexity limits the practical application of SRP-PHAT. For a microphone array, each location corresponds to a set of time differences of arrival (TDOAs), and this paper collects them into a TDOA vector. Since the TDOA vectors in the adjacent regions are similar, we present a fast algorithm based on clustering search to reduce the computation complexity of SRP-PHAT. In the training stage, the K-means or Iterative Self-Organizing Data Analysis Technique (ISODATA) clustering algorithm is used to find the centroid in each cluster with similar TDOA vectors. In the procedure of sound localization, the optimal cluster is found by comparing the steered response powers (SRPs) of all centroids. The SRPs of all candidate locations in the optimal cluster are compared to localize the sound source. Experiments both in simulation environments and real environments have been performed to compare the localization accuracy and computational load of the proposed method with those of the the conventional SRP-PHAT algorithm. The results show that the proposed method is able to reduce the computational load drastically and maintained almost the same localization accuracy and robustness as those of the conventional SRP-PHAT algorithm. The difference in localization performance by different clustering algorithms used in the training stage is trivial.