The depth modeling mode (DMM) is a new coding tool in the three-dimensional extension of high-efficiency video coding (3D-HEVC) standard to improve the coding of depth maps. In DMM, the current depth block is partitioned into two nonrectangular partitions and each partition is predicted by a constant partition value (CPV). A searching algorithm for the optimal CPVs has been provided in the 3D-HEVC reference software, which, however, has high complexity and is time-consuming. This letter shows that the distortion function in DMM is convex and proposes a fast early termination algorithm for searching the optimal CPVs without losing its optimality. Theoretical analysis of the method is provided, and experimental results show that our method can save 20% of search time with the same coding performance.