The multi-robot search problem is challenging since it involves task allocation, minimal routing, and maximal coverage problems, which are NP-hard. To solve this problem with theoretical guarantees, it is reformulated as a maximal coverage problem subject to the intersection of matroid constraints. The coverage problem is solved by utilizing its submodularity. Additionally, the workload balance is considered to enhance search efficiency. The intersection matroid is composed of a routing constraint and a clustering constraint. The proposed algorithm, Multi-Robot Search with Matroid constraints (MRSM), achieves ( 1 / 3 ) O P T ˜ , where O P T ˜ is the optimal performance under spanning-tree structures. Furthermore, Dynamic MRSM (D-MRSM) and MRSM with Hexagonal Packing (MRSM-Hex) are proposed for unknown and large-scale environments, respectively. The experiment results show that the MRSM approaches outperform state-of-the-art methods in terms of expected time to detection in multi-robot search problems and scale effectively for large search spaces.