High-dimensional change point detection problems pose several challenges. First, we discuss computational challenges whenever underlying model fits are expensive and propose a widely applicable new methodology, called optimistic binary segmentation, that has the potential for massive computational savings while maintaining good statistical performance. In the second part, we discuss the commonly occurring phenomenon of missing values and why this poses particular challenges in heterogeneous populations, i.e., in the presence of change points. Specifically, we propose estimation methods for change points in high-dimensional covariance structures and advocate three imputation methods for scenarios with missing values. We investigate implications on common losses used for change point detection, with an emphasis on the applicability of optimistic binary segmentation in such challenging scenarios with missing values. We also discuss how model selection methods have to be adapted to the setting of incomplete data. The methods are compared in a simulation study and applied to detect changes in time series from an environmental monitoring system with naturally occurring missing values.