Motivated by the goal of improving the efficiency of small sample design, we propose a novel Bayesian stochastic approximation method to estimate the root of a regression function. The method feature adap- tive local modelling and non-recursive iteration. Strong consistency of the Bayes estimator is obtained. Simulation studies show that our met- hod is superior in finite-sample performance to Robbins-Monro type procedures. Extensions to searching for extreme and a version of gen- eralized multivariate quantile are presented.