Frontiers of search in heterogeneous environments: From Markovian to Non-Markovian dynamics