Current practice for maritime search and rescue (MSAR) adheres to predetermined full-coverage patterns for finding targets. These do not account for key success factors for MSAR missions such as the dynamic location of targets, updates on situational awareness during mission execution, and search vehicle kinematics. Consequently, current practice cannot incorporate realistic MSAR operational conditions into path-finding, increasing the likelihood of mission failure. To address this issue, a novel, flexible path-finding framework is proposed for generating a path while dynamically updating the probability of a target based on the path's trajectories. The solution approach implements the A* algorithm, which can accommodate the dynamics of a vehicle and guarantees the optimality of the final path with respect to the target objective function. Experiments show that a more than 50% improvement in the time needed to guarantee a certain probability of finding a target is exhibited compared to the parallel sweep coverage path-finding approach.