According to the Centers for Disease Control and Prevention (CDC), one in twenty five hospital patients are infected with at least one healthcare acquired infection (HAI) on any given day. Early detection of possible HAI outbreaks help practitioners implement countermeasures before the infection spreads extensively. Here, we develop an efficient data and model driven method to detect outbreaks with high accuracy. We leverage mechanistic modeling of C. difficile infection, a major HAI disease, to simulate its spread in a hospital wing and design efficient near-optimal algorithms to select people and locations to monitor using an optimization formulation. Results show that our strategy detects up to 95% of future C. difficile outbreaks. We design our method by incorporating specific hospital practices (like swabbing for infections) as well. As a result, our method outperforms state-of-the-art algorithms for outbreak detection. Finally, a qualitative study of our result shows that the people and locations we select to monitor as sensors are intuitive and meaningful.