We propose an exact binary search-based branch-and-bound algorithm, termed the Quadtree Search Method, for solving bi-objective integer programs. The existing literature on criterion space search methods for multi-objective optimization predominantly assumes that subproblems can be solved to optimality, an assumption that becomes computationally prohibitive for hard instances. In contrast, our approach departs from this assumption by prioritizing feasibility checks over optimality at each subproblem, while still guaranteeing eventual generation of the entire nondominated frontier. The proposed method extends binary search by introducing an additional undecided state for time-limited subproblems, thereby preventing the search from stalling on computationally challenging nodes. We further incorporate several enhancements, including initial bounds, warm starts, dynamic upper bound tightening, and the selective skipping of redundant feasibility checks. We demonstrate the efficacy of the proposed method on bi-objective assignment, set covering, and traveling salesman problems. The results show that the Quadtree Search Method is particularly effective on difficult instances, providing provable quality guarantees for the approximated nondominated frontier even when terminated prematurely