Motivated by surgical applications, we consider a minimum cost search for a target, whose precise location is uncertain. The region of interest is divided into grid cells and the searcher may take one of two actions on a cell: 1) cut into the cell, which is quick but bears the risk of damaging the target; or 2) explore the cell, which is time consuming but safely resolves uncertainty regarding whether the target is in that cell. We study two formulations of this problem: the unconstrained search, in which the searcher may visit cells in any order, and the constrained search, in which the searcher may only visit adjacent cells. We prove that the optimal policy for the unconstrained search problem can be obtained in polynomial time, and we propose two suboptimal policies for the constrained search that take advantage of the unconstrained solution. We present computational results based on minimally invasive kidney surgery.