Hybrid videos that contain periodic low-resolution (LR) frames and high-resolution (HR) guide frames are largely used for the consideration of bandwidth efficiency and the tradeoff between spatial and temporal resolution. Super-resolution (SR) algorithms are necessary to refine the LR frames, in which non-local means (NLM) is a promising algorithm. NLM replaces every pixel with a weighted average of its neighbors based on non-local self-similarity between pixels. However, the fixed decaying factor of NLM cannot satisfy regions of distinct characteristics in LR frames. The fixed neighborhood or the so-called searching window fails to balance the requirements of low computation and advanced video quality. In this paper, we propose novel criteria to choose the parameters adaptively. The decaying factor is defined by patch difference of a pixel and guarantees NLM to find relevant pixels. Two methods, namely a predefined method inspired by motion estimation and an exhaustive method by searching progressively enlarged neighborhood are proposed to determine the neighborhood size. Bilateral adjacent HR guide frames are used to handle the occlusion problem. We also analyze the defined patch difference on pixel-, frame-, and sequence-level and reveal its influence on the algorithm. The experimental results verify the validity of the proposed method.