{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T12:32:22Z","timestamp":1765369942505,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2021,12,26]],"date-time":"2021-12-26T00:00:00Z","timestamp":1640476800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Given a monotone ordered multi-dimensional real array A and a real value k, an important question in computation is to establish if k is a member of A by sequentially searching A by comparing k with some of its entries. This search problem and its known results are surveyed, including the case when A has sizes not necessarily equal. Worst case search algorithms for various types of arrays of finite dimension and sizes are reported. Each algorithm has order strictly less than the product of the sizes of the array. Present challenges and open problems in the area are also presented.<\/jats:p>","DOI":"10.3390\/a15010010","type":"journal-article","created":{"date-parts":[[2021,12,27]],"date-time":"2021-12-27T01:00:54Z","timestamp":1640566854000},"page":"10","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Searching Monotone Arrays: A Survey"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1888-7802","authenticated-orcid":false,"given":"M\u00e1rcia R.","family":"Cappelle","sequence":"first","affiliation":[{"name":"Instituto de Inform\u00e1tica, Universidade Federal de Goi\u00e1s, Goi\u00e2nia 74690-900, Brazil"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7538-8263","authenticated-orcid":false,"given":"Les R.","family":"Foulds","sequence":"additional","affiliation":[{"name":"Instituto de Inform\u00e1tica, Universidade Federal de Goi\u00e1s, Goi\u00e2nia 74690-900, Brazil"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0712-7376","authenticated-orcid":false,"given":"Humberto J.","family":"Longo","sequence":"additional","affiliation":[{"name":"Instituto de Inform\u00e1tica, Universidade Federal de Goi\u00e1s, Goi\u00e2nia 74690-900, Brazil"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,26]]},"reference":[{"key":"ref_1","unstructured":"Baase, S., and Gelder, A.V. (2000). Computer Algorithms: Introduction to Design and Analysis, Addison-Wesley. [3rd ed.]."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0304-3975(89)90027-3","article-title":"Complexity of selection in X+Y","volume":"67","author":"Cosnard","year":"1989","journal-title":"Theor. Comput. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Gries, D. (1981). The Science of Programming, Springer. Texts and Monographs in Computer Science.","DOI":"10.1007\/978-1-4612-5983-1"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Sarnath, R., and He, X. (1992). Efficient parallel algorithms for selection and searching on sorted matrices. Parallel Processing Symposium, International, IEEE Computer Society.","DOI":"10.1109\/IPPS.1992.223063"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0196-6774(85)90020-3","article-title":"Searching ordered structures","volume":"6","author":"Linial","year":"1985","journal-title":"J. Algorithms"},{"key":"ref_6","unstructured":"Dijkstra, E.W. (1976). A Discipline of Programming, Prentice-Hall, Inc.. [1st ed.]."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/11783596_8","article-title":"Improving saddleback search: A lesson in algorithm design","volume":"Volume 4014","author":"Uustalu","year":"2006","journal-title":"Proceedings of the Mathematics of Program Construction: 8th International Conference, MPC 2006"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/S0304-3975(97)00027-3","article-title":"Optimal algorithms for generalized searching in sorted matrices","volume":"188","author":"Shen","year":"1997","journal-title":"Theor. Comput. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"2213","DOI":"10.1016\/j.disc.2007.04.067","article-title":"Searching monotone multi-dimensional arrays","volume":"308","author":"Cheng","year":"2008","journal-title":"Discret. Math."},{"key":"ref_10","unstructured":"Knuth, D.E. (1973). The Art of Computer Programming: Sorting and Searching, Addison-Wesley Pub. Co.. [1st ed.]. Addison-Wesley Series in Computer Science and Information Processing."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1145\/359619.359623","article-title":"Jump Searching: A Fast Sequential Search Technique","volume":"21","author":"Shneiderman","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_12","unstructured":"Martin, J. (1977). Computer Data-Base Organization, Prentice-Hall. [2nd ed.]. Prentice-Hall Series in Automatic Computation."},{"key":"ref_13","unstructured":"Patterson, G.W. (1946). Sorting and collating. Theory and Techniques for the Design of Electronic Digital Computers, University of Pennsylvania. Lecture 22."},{"key":"ref_14","unstructured":"Steinhaus, H. (1960). Mathematical Snapshots, Oxford University Press. [3rd ed.]."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"133","DOI":"10.2307\/2312475","article-title":"On an optimal search procedure","volume":"68","author":"Sandelius","year":"1961","journal-title":"Am. Math. Mon."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Reingold, E.M. (1972, January 16\u201318). Establishing lower bounds on algorithms: A survey. Proceedings of the Spring Joint Computer Conference, Atlantic City, NJ, USA.","DOI":"10.1145\/1478873.1478936"},{"key":"ref_17","unstructured":"Dijkstra, E.W. (2021, December 23). EWD1293\u2014Constructing the Binary Search Once More. Department of Computer Sciences, The University of Texas at Austin: Austin, TX, USA. Available online: http:\/\/www.cs.utexas.edu\/users\/EWD\/ewd12xx\/EWD1293.PDF."},{"key":"ref_18","first-page":"6","article-title":"Indexing for rapid random access memory systems","volume":"5","author":"Dumey","year":"1956","journal-title":"Comput. Autom."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/368699.368705","article-title":"Variable-width tables with binary-search facility","volume":"1","author":"Halpern","year":"1958","journal-title":"Commun. ACM"},{"key":"ref_20","unstructured":"McCracken, D.D. (1957). Digital Computer Programming, John Wiley & Sons. General Electric Series."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Lehmer, D.H. (1960). Teaching combinatorial tricks to a computer. Combinatorial Analysis, American Mathematical Society.","DOI":"10.1090\/psapm\/010\/0113289"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1093\/comjnl\/26.2.154","article-title":"Some Lessons Drawn from the History of the Binary Search Algorithm","volume":"26","author":"Lesuisse","year":"1983","journal-title":"Comput. J."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1145\/321119.321120","article-title":"Structure and Use of ALGOL 60","volume":"9","author":"Bottenbruch","year":"1962","journal-title":"J. ACM"},{"key":"ref_24","unstructured":"Iverson, K.E. (1962). A Programming Language, John Wiley & Sons, Inc."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1145\/367593.367620","article-title":"Computer-drawn Flowcharts","volume":"6","author":"Knuth","year":"1963","journal-title":"Commun. ACM"},{"key":"ref_26","unstructured":"Hesselink, W.H. (2021, December 23). whh303\u2014Ternary Search. Dept. of Mathematics and Computing Science, Rijksuniversiteit Groningen: Groningen, The Netherlands. Available online: http:\/\/wimhesselink.nl\/pub\/whh303.pdf."},{"key":"ref_27","unstructured":"Kostyukov, V. (2021, December 04). Dual-Pivot Binary Search. Available online: https:\/\/kostyukov.net\/posts\/dual-pivot-binary-search\/."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1147\/rd.12.0130","article-title":"Addressing for Random-Access Storage","volume":"1","author":"Peterson","year":"1957","journal-title":"IBM J. Res. Dev."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1145\/359545.359557","article-title":"Interpolation Search\u2014A loglogN Search","volume":"21","author":"Perl","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1016\/0020-0190(76)90071-5","article-title":"An almost optimal algorithm for unbounded searching","volume":"5","author":"Bentley","year":"1976","journal-title":"Inf. Process. Lett."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"648","DOI":"10.1145\/367487.367496","article-title":"Fibonaccian Searching","volume":"3","author":"Ferguson","year":"1960","journal-title":"Commun. ACM"},{"key":"ref_32","unstructured":"Aggarwal, A., Klawe, M., Moran, S., Shor, P., and Wilber, R. Geometric Applications of a Matrix Searching Algorithm. Proceedings of the Second Annual Symposium on Computational Geometry."},{"key":"ref_33","unstructured":"Cappelle, M.R., Foulds, L.R., and Longo, H.J. (2017). A note on searching sorted unbalanced three-dimensional arrays. arXiv."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/1\/10\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:53:38Z","timestamp":1760169218000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/1\/10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,26]]},"references-count":33,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,1]]}},"alternative-id":["a15010010"],"URL":"https:\/\/doi.org\/10.3390\/a15010010","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,12,26]]}}}