{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:29:33Z","timestamp":1787340573056,"version":"build-2736575974"},"reference-count":7,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,11]]},"abstract":"<jats:p>A \u201csemisorted table\u201d is a one-dimensional array containing n data, which are not necessarily sorted, but can appear in p different permutations of the ascending order. We consider the problem of searching in such a table without knowing, in which one of the p permutations the data are stored (SST). It is shown that any deterministic search algorithm for SST needs at least $\\sqrt[n]{p}$ comparisons in the worst case. This lower bound is generalized to average case performance even for nondeterministic algorithms. Some examples are given where the lower bound is tight.<\/jats:p>","DOI":"10.1137\/0214059","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"840-848","source":"Crossref","is-referenced-by-count":5,"title":["Searching Semisorted Tables"],"prefix":"10.1137","volume":"14","author":[{"given":"Helmut","family":"Alt","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kurt","family":"Mehlhorn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"RAMM","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90098-X"},{"key":"RB","unstructured":"A. Borodin, Oral communication"},{"key":"RLS","doi-asserted-by":"crossref","unstructured":"N. Linial, M. E. Saks,  Information bounds are good for search problems on ordered data structures,  Proc. 24th IEEE Symposium on Foundations of Computer Science, Tucson, AZ,  1983,  473\u2013475","DOI":"10.1109\/SFCS.1983.27"},{"key":"RM","unstructured":"J. I. Munro,  A multikey search problem,  Proc.17th Annual Allerton Conference, October,  1979 0764.68019"},{"key":"RMS","doi-asserted-by":"crossref","unstructured":"J. I. Munro, H. Suwanda,  Implicit data structures,  Proc.11th Annual ACM Symposium on Theory of Computing,  1979,  108\u2013117, May","DOI":"10.1145\/800135.804404"},{"key":"RR","doi-asserted-by":"publisher","DOI":"10.1137\/0205003"},{"key":"RY","doi-asserted-by":"crossref","unstructured":"A. C. Yao,  Should tables be sorted?  Proc. IEEE Symposium on Foundations of Computer Science,  1978,  22\u201327","DOI":"10.1109\/SFCS.1978.33"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214059","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:54Z","timestamp":1787337594000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214059"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,11]]},"references-count":7,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1985,11]]}},"alternative-id":["10.1137\/0214059"],"URL":"https:\/\/doi.org\/10.1137\/0214059","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,11]]}}}