Public Phone application is the application that contains telephone numbers of public services, as well as equipped with emergency telephone numbers such as telephone numbers police stations, fire stations, hospitals and many other agencies offices. Phone public service also includes the address and google maps feature to find out where we are located as well as the location of a public office who want to visit in the area such as the solution of the problems in communicating. In making the application of the Public Service Telephone Kendari required algorithm or method that is effective, because the search process is one important part of the data processing. The algorithm used is Interpolation Search. Interpolation Search is a search algorithm that is more efficient than the algorithms Binary and Sequential Search. This is because the algorithm is no need to explore every element of the table. On the menu there is a phone text auto-complete feature that allows users to search for the name of the agency in question. Results of this research is the Public Service Telephone applications Kendari implemented on Android Operating System and built using the Android programming language. Keywords— Public Phone, Interpolation Search, Auto Complete Text, Android