Abstract

It consider the problem of computing efficient strategies for Searching. As a generalization of the classical binary search for ordered array, suppose one wishes to find a specific element in an ordered array by making comparisons, where each comparison indicates the endpoint closer to the desired element. Given the likelihood of each element being the one searched, the objective is to compute a search strategy that minimizes the expected number of comparisons. Practical applications of this problem include file system synchronization and software testing. Here this paper presents a new algorithm which is 2 times faster than classical Binary Search. This represents a significant improvement over previous Binary Search Algorithm having worst case complexity O(log n). This New algorithm Quadratic Search having worst case complexity O(log n/2). It is shown in this paper that by splitting and checking the ordered array in a way that the searching speed of a specific element is twice than the classical Binary search.

References

• An Approximation Algorithm for Binary Searching in Trees duardo Laber Marco Molinaro : Algorithmica (2011) 59: 601–620 DOI 10. 1007/s00453-009-9325-0
• D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching. Reading, MA: Addison-Wesley,1973 Structures.
• E. Horowitz and S. Sahni, fundamental of Data Structure Rockville, MD: Computer Science Press, 1982.
• K. J. Overholt, "Optimal binary search methods," BIT, vol. 13, no. 1, pp. 84-91, 1973.
• D. Coppersmith, "Fast evaluation of logarithms in finite fields of characteristic two," IEEE Trans. Inform. Theory, vol. IT-30, pp. 587-594, 1984.
• Ben-Asher, Y. , Farchi, E. , Newman, I. : Optimal search in trees. SIAM J. Comput. 28(6), 2090–2102 (199Carmo, R. , Donadelli, J. , Kohayakawa, Y. , Laber, E. : Searching in random partially ordered sets. Theor. Comput. Sci. 321(1), 41–57 (2004)
• Knight, W. : Search in an ordered array having variable probe cost. SIAM J. Comput. 17(6), 1203–1214 (1988)
• Navarro, G. , Baeza-Yates, R. , Barbosa, E. , Ziviani, N. , Cunto, W. : Binary searching with nonuniform costs and its application to text retrieval. Algorithmica 27(2), 145–169 (2000)
• The ??-Version of Binary Search Trees: An Average Case Analysis, Hindawi Publishing CorporationISRN Combinatorics,Volume 2013, Article ID 450627, 8 pages,http://dx. doi. org/10. 1155/2013/450627
• Machine Vision and Applications,DOI 10. 1007/s00138-013-0483-3A 3-degree of freedom binary search pose estimation technique,Robert Ross • Andrew Martchenko • John Devlin,Received: 18 September 2011 / Revised: 29 October 2012 / Accepted: 11 january 2013,© Springer-Verlag Berlin Heidelberg 2013
• IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. SE-5, NO. 4, JULY 1979,Multidimensional Binary Search Trees in Database Applications,JON L. BENTLEY, MEMBER, IEEE
• Non-blocking Binary Search Trees, PODC'10, July 25–28, 2010, Zurich, Switzerland. Copyright 2010 ACM 978-1-60558-888-9/10/07 . . . $10. 00.
• A Non-Blocking Internal Binary Search Tree,SPAA'12, June 25–27, 2012, Pittsburgh, Pennsylvania, USA. Copyright 2012 ACM 978-1-4503-1213-4/12/06 . . . $10. 00.
• Noisy binary search and its applications,Computer Science Division, University of California, Berkeley. Supported in part by NSF grant CCF-0515259 karp@icsi. berkeley. edu, rdk@cs. cornell. edu