Over the decades, variable selection with high-dimensional data has drawn increasing attention. With large number of predictors, it rises a big challenge for model fitting and prediction. In this study, we develop a new Bayesian approach to best subset selection that quickly finds the best subset via a hybrid search algorithm of deterministic local search and stochastic global search. To avoid the computational burden to evaluate multiple candidate subsets for each update, we propose a novel computing strategy that enables us to calculate exact posterior probabilities of all neighbor models simultaneously. We also discuss model selection consistency of proposed method in the high-dimensional setting in which the number of possible predictors can increase faster than the sample size. Simulation study and real data example are shown to investigate the performance of the newly-developed method.