Many natural processes rely on optimizing the success ratio of an underlying search process. We investigate how fluxes of information between individuals and their environment modify the statistical properties of human search strategies. Using an online game, searchers have to find a hidden target whose location is hinted by a surrounding neighborhood. Searches are optimal for intermediate neighborhood sizes; smaller areas are harder to locate while larger ones obscure the location of the target inside it. Although the neighborhood size that minimizes average search times depends on neighborhood geometry, we develop a theoretical framework to predict this value in a general setup. Furthermore, a priori access to information about the landscape turns search strategies into self-adaptive processes in which the trajectory on the board evolves to show a well-defined characteristic jumping length. A family of random-walk models is developed to investigate the non-Markovian nature of the process.