CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Quadratic Search: A New and Fast searching Algorithm (An extension of classical Binary search strategy)

by Parveen Kumar
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 65 - Number 14
Year of Publication: 2013
Authors: Parveen Kumar
10.5120/10996-6165

Parveen Kumar . Quadratic Search: A New and Fast searching Algorithm (An extension of classical Binary search strategy). International Journal of Computer Applications. 65, 14 ( March 2013), 43-46. DOI=10.5120/10996-6165

@article{ 10.5120/10996-6165,
author = { Parveen Kumar },
title = { Quadratic Search: A New and Fast searching Algorithm (An extension of classical Binary search strategy) },
journal = { International Journal of Computer Applications },
issue_date = { March 2013 },
volume = { 65 },
number = { 14 },
month = { March },
year = { 2013 },
issn = { 0975-8887 },
pages = { 43-46 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume65/number14/10996-6165/ },
doi = { 10.5120/10996-6165 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:18:51.868823+05:30
%A Parveen Kumar
%T Quadratic Search: A New and Fast searching Algorithm (An extension of classical Binary search strategy)
%J International Journal of Computer Applications
%@ 0975-8887
%V 65
%N 14
%P 43-46
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
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
  1. An Approximation Algorithm for Binary Searching in Trees duardo Laber Marco Molinaro : Algorithmica (2011) 59: 601–620 DOI 10. 1007/s00453-009-9325-0
  2. D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching. Reading, MA: Addison-Wesley,1973 Structures.
  3. E. Horowitz and S. Sahni, fundamental of Data Structure Rockville, MD: Computer Science Press, 1982.
  4. K. J. Overholt, "Optimal binary search methods," BIT, vol. 13, no. 1, pp. 84-91, 1973.
  5. D. Coppersmith, "Fast evaluation of logarithms in finite fields of characteristic two," IEEE Trans. Inform. Theory, vol. IT-30, pp. 587-594, 1984.
  6. 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)
  7. Knight, W. : Search in an ordered array having variable probe cost. SIAM J. Comput. 17(6), 1203–1214 (1988)
  8. 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)
  9. 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
  10. 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
  11. IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. SE-5, NO. 4, JULY 1979,Multidimensional Binary Search Trees in Database Applications,JON L. BENTLEY, MEMBER, IEEE
  12. 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.
  13. 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.
  14. 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
Index Terms

Computer Science
Information Sciences

Keywords

Binary Search Complexity analysis

Powered by PhDFocusTM