Unconditional exact tests are increasingly used in practice for categorical data to increase the power of a study and to make the data analysis approach being consistent with the study design. In a two-arm study with a binary endpoint, p-value based on the exact unconditional Barnard test is computed by maximizing the tail probability over a nuisance parameter with a range from 0 to 1. The traditional grid search method is able to find an approximate maximum with a partition of the parameter space, but it is not accurate and this approach becomes computationally intensive for a study beyond two groups. We propose using a polynomial method to rewrite the tail probability as a polynomial. The solutions from the derivative of the polynomial contain the solution for the global maximum of the tail probability. We use an example from a double-blind randomized Phase II cancer clinical trial to illustrate the application of the proposed polynomial method to achieve an accurate p-value. We also compare the performance of the proposed method and the traditional grid search method under various conditions. We would recommend using this new polynomial method in computing accurate exact unconditional p-values.