The coarse-to-fine search strategy is extensively used in current reported research. However, it has the same problem as any hill climbing algorithm, most importantly, it often finds local instead of global minima. Drawing upon the artificial intelligence literature, we applied an optimal graph search, namely A*, to the problem. Using real stereo and video test sets, we compared the A* method to both template and hill climbing. Our results show that A* has greater accuracy than the ubiquitous coarse-to-fine hill climbing pyramidal search algorithm in both stereo matching and motion tracking.