Contemporary quantum algorithms, being efficient theoretically, fail to run on real QPUs. One reason for these failures is the algorithm’s probabilistic nature, which is amplified by imperfections in hardware implementation. Grover search is such a probabilistic method, which enables other methods in quantum optimization and machine learning. In this work we improve the theoretical worst case complexity of Grover Adaptive Search by replacing iterations with binary search. We observe in the experiments that our method shows better success rate in general, and is sufficiently better for a specific type of optimization landscapes with plateaus.