Protein complexes involved in DNA mismatch repair diffuse along dsDNA as sliding clamps in order to locate a hemimethylated incision site. They have been observed to use a dissociative mechanism, in which two proteins, while continuously remaining attached to the DNA, sometimes associate into a single complex sliding on the DNA and sometimes dissociate into two independently sliding proteins. Here, we study the probability that these complexes locate a given target site via a semi-analytic, Monte Carlo calculation that tracks the association and dissociation of the sliding complexes. We compare such probabilities to those obtained using a nondissociative diffusive scan in the space of physically realistic diffusion constants, hemimethylated site distances, and total search times to determine the regions in which dissociative searching is more or less efficient than nondissociative searching. We conclude that the dissociative search mechanism is advantageous in the majority of the physically realistic parameter space, suggesting that the dissociative search mechanism confers an evolutionary advantage.