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

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

ASH Search: Binary Search Optimization

by Ashar Mehmood
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 178 - Number 15
Year of Publication: 2019
Authors: Ashar Mehmood
10.5120/ijca2019918788

Ashar Mehmood . ASH Search: Binary Search Optimization. International Journal of Computer Applications. 178, 15 ( May 2019), 10-17. DOI=10.5120/ijca2019918788

@article{ 10.5120/ijca2019918788,
author = { Ashar Mehmood },
title = { ASH Search: Binary Search Optimization },
journal = { International Journal of Computer Applications },
issue_date = { May 2019 },
volume = { 178 },
number = { 15 },
month = { May },
year = { 2019 },
issn = { 0975-8887 },
pages = { 10-17 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume178/number15/30604-2019918788/ },
doi = { 10.5120/ijca2019918788 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-07T00:50:27.968322+05:30
%A Ashar Mehmood
%T ASH Search: Binary Search Optimization
%J International Journal of Computer Applications
%@ 0975-8887
%V 178
%N 15
%P 10-17
%D 2019
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The binary search is a method of finding the position of an element in an ordered array. It continuously aims the middle element of array and check if it is the target element or not untills it finds its position. The best case complexity of binary search is O(1), whereas average and worst case time complexity is O(log n), where ‘n’ is the number of elements in the array. In this paper, I have proposed an algorithm which drastically improves the complexity of search algorithm in sorted array domain outperforming binary search, the paper also compares the proposed solution with other well-known search algorithms. The presented approach minimizes the space complexity, eliminates the need to analyze the scenario and look for the algorithm that best fits the given problem. The proposed algorithm has constant space complexity (O(1)) and time complexity of O(1) (constant time) in best case, O(log(log n)) in average case and O(log(n)) in worst case. Thus, most of the time proposed algorithm works very well as compared to other search algorithms in sorted array domain.

References
  1. D. E. Knuth, “The Art of Computer Programming”, Vol. 3: Sorting and Searching, Addison Wesley, 1973.
  2. F. Plavec, Z. G. Vranesic, Stephen D. Brown, “On Digital Search Trees: A Simple Method for Constructing Balanced Binary Trees”, in Proceedings of the 2 nd International Conference on Software and Data Technologies (ICSOFT ’07), Vol. 1, Barelona, Spain, July 2007, pp. 61-68.
  3. W. W. Peterson, “Addressing for Random-Access Storage”, IBM Journal of Research & Development, doi: 10.1147/rd.12.0130, 1957.
  4. Ben Shneiderman, “Jump Searching: A Fast Sequential Search Technique”, Communications of the ACM, Vol. 21, NY, USA, Octuber 1978, pp. 831-834, doi: 10.1145/359619.359623.
  5. Phisan Kaewprapha, Thaewa Tansarn, Nattankan Puttarak, “Network localization using tree search algorithm: A heuristic search via graph properties”, 13 th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON), 2016.
  6. Parveen Kumar, “Quadratic Search: A New and Fast Searching Algorithm (An extension of classical Binary search strategy)”, International Journal of Computer Applications, Vol. 65, Hamirpur Himachal Pradesh, India, March 2013.
  7. Hermann Von Schmid, “Decimal Computation (1 st ed)”, John Wiley & Sons Ins., NY, USA, 1974.
  8. J. L. Bentley, A. C. Yao, “An almost optimal algorithm for unbounded searching”, Vol. 5, Issue 3, Information Processing Letters, pp. 82-87, doi: 10.1016/0020-0190(76)90071-5, ISSN 0020-0190, 1976.
  9. B. Chazelle, L. J. Guibas, “Fractional cascading: A data structuring technique”, Algorithmica, Vol. 1, Issue 1-4, pp. 133-162, November 1986.
  10. Franco P. Preparata, Michael Ian Shamos, “Computational Geometry - An Introduction”, ISBN 3-540-96131-3, 1988.
  11. Jaiwei Han, Micheline Kamber, Jian Pei, “Data Mining: Concepts and Techniques (3 rd ed.)”, ISBN: 978-0-12-381479-1, June 2011.
  12. Vladimir Korepin, Ying Xu, “Binary Quantum Search”, International Journal of Modern Physics B, Vol. 21, ISSN 5187-5205, doi: 10.1117/12.717282, May 2007.
  13. Andrzej Pelc, “Searching with known error probability”, Theoretical Computer Science, pp. 1855-2022, doi: 10.1016/0304-3975(89)90077-7, 1989.
  14. R. L. Rivest, A. R. Meyer, D. J. Kleitman, “Coping with errors in binary search procedures”, STOC ’78 Proceedings of the 10 th annual ACM symposium on Theory of computing, doi: 10.1145/800133.804351, pp. 227-232, San Diego, California, USA, 1978.
  15. David E. Ferguson, “Fibonaccian searching”, Communications of ACM, Vol. 3, Issue 12, NY, USA, doi: 10.1145/367487.367496, 1960.
  16. Kevin lenzo, “The CMU Pronouncing Dictionary”, Speech at CMU, Retrieved Aug 13, 2018 from url: http://www.speech.cs.cmu.edu/cgi-bin/cmudict.
Index Terms

Computer Science
Information Sciences

Keywords

Binary search Sorted searching Search optimization Interpolation search complexity analysis.

Powered by PhDFocusTM