{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T05:01:49Z","timestamp":1780030909836,"version":"3.53.1"},"reference-count":33,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Information Processing Letters"],"published-print":{"date-parts":[[2026,8]]},"DOI":"10.1016\/j.ipl.2026.106640","type":"journal-article","created":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T03:40:44Z","timestamp":1774928444000},"page":"106640","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Optimal average-case binary search with outcome-dependent costs"],"prefix":"10.1016","volume":"194","author":[{"given":"Roberto","family":"Bruno","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roberto","family":"De Prisco","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4085-7300","authenticated-orcid":false,"given":"Ugo","family":"Vaccaro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.ipl.2026.106640_bib0001","series-title":"Which Way Did the Bicycle Go?: And Other Intriguing Mathematical Mysteries","author":"Konhauser","year":"1966"},{"key":"10.1016\/j.ipl.2026.106640_bib0002","unstructured":"https:\/\/www.freecodecamp.org\/news\/how-to-solve-the-google-recruiters-puzzle-about-throwing-eggs-from-a-building-de6e7ef1755d."},{"key":"10.1016\/j.ipl.2026.106640_bib0003","unstructured":"X. Cao, Z. Chen, S.J. Miller, Egg drop problems: they are all they are cracked up to be, 2025. https:\/\/arxiv.org\/abs\/2511.18330."},{"key":"10.1016\/j.ipl.2026.106640_bib0004","unstructured":"K. Papadopoulos, An O(log\u2009N) time algorithm for the generalized egg dropping problem, arxiv: 2602.22870[cs.ds edition, 2026."},{"key":"10.1016\/j.ipl.2026.106640_bib0005","series-title":"LNCS","article-title":"Guessing games and distributed computations in synchronous networks","volume":"267","author":"Leeuwen","year":"1987"},{"key":"10.1016\/j.ipl.2026.106640_bib0006","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/0022-0000(82)90005-8","article-title":"A general class of resource tradeoffs","volume":"25","author":"Bentley","year":"1982","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.ipl.2026.106640_bib0007","article-title":"Data Structures and Algorithms 1: Sorting and Searching","author":"Mehlhorn","year":"1984"},{"key":"10.1016\/j.ipl.2026.106640_bib0008","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/BF00264289","article-title":"Optimum binary search trees","volume":"1","author":"Knuth","year":"1971","journal-title":"Acta Inf."},{"key":"10.1016\/j.ipl.2026.106640_bib0009","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1137\/0603055","article-title":"Speed-up in dynamic programming","volume":"3","author":"Yao","year":"1982","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10.1016\/j.ipl.2026.106640_bib0010","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1137\/0121057","article-title":"Optimal computer search trees and variable-length alphabetical codes","volume":"21","author":"Hu","year":"1971","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/j.ipl.2026.106640_bib0011","series-title":"Search Problems","author":"Ahlswede","year":"1987"},{"key":"10.1016\/j.ipl.2026.106640_bib0012","series-title":"IEEE International Symposium on Information Theory (ISIT)","first-page":"1","article-title":"Optimal binary variable-length codes with a bounded number of 1\u2019s per codeword: design, analysis, and applications","author":"Bruno","year":"2025"},{"key":"10.1016\/j.ipl.2026.106640_bib0013","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1137\/0203008","article-title":"Optimal binary search trees with restricted maximal depth","volume":"3","author":"Garey","year":"1974","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/j.ipl.2026.106640_bib0014","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1137\/0205002","article-title":"Optimal alphabetic trees","volume":"5","author":"Itai","year":"1976","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.ipl.2026.106640_bib0015","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/0020-0190(76)90052-1","article-title":"Optimal alphabetic search trees with restricted maximal height","volume":"4","author":"Wessner","year":"1976","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"10.1016\/j.ipl.2026.106640_bib0016","doi-asserted-by":"crossref","first-page":"1770","DOI":"10.1109\/18.705558","article-title":"A dynamic programming algorithm for constructing optimal prefix-free codes with unequal letter costs","volume":"44","author":"Golin","year":"1998","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10.1016\/j.ipl.2026.106640_bib0017","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1016\/j.ejor.2017.07.031","article-title":"Operations research applications of dichotomous search","volume":"265","author":"Hassin","year":"2018","journal-title":"Eur. J. Oper. Res."},{"key":"10.1016\/j.ipl.2026.106640_bib0018","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1109\/TIT.1961.1057615","article-title":"Minimum-redundancy coding for the discrete noiseless channel","volume":"7","author":"Karp","year":"1961","journal-title":"IRE Trans. Inf. Theory"},{"issue":"3","key":"10.1016\/j.ipl.2026.106640_bib0019","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1145\/65950.65955","article-title":"Optimum lopsided binary trees","volume":"36","author":"Kapoor","year":"1989","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/j.ipl.2026.106640_bib0020","first-page":"59","article-title":"Group-sequential leak-testing of sealed radium sources","volume":"18","author":"Pasternack","year":"1975","journal-title":"Technometrics"},{"key":"10.1016\/j.ipl.2026.106640_bib0021","first-page":"512","article-title":"Auditing: active learning with outcome-dependent query costs","volume":"26","author":"Sabato","year":"2013","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"10.1016\/j.ipl.2026.106640_bib0022","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1016\/j.tcs.2017.12.033","article-title":"Submodular learning and covering with response-dependent costs","volume":"742","author":"Sabato","year":"2018","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.ipl.2026.106640_bib0023","doi-asserted-by":"crossref","unstructured":"A.M. Saettler, E.S. Laber, F. Cicalese, Trading off worst and expected cost in decision tree problems and a value dependent model, arxiv: 1406.3655 edition, 2014.","DOI":"10.1007\/978-3-662-48971-0_20"},{"key":"10.1016\/j.ipl.2026.106640_bib0024","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1016\/j.ipl.2015.02.006","article-title":"Approximating decision trees with value-dependent testing costs","volume":"115","author":"Saettler","year":"2015","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/j.ipl.2026.106640_bib0025","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/S0020-0190(98)00166-5","article-title":"Binary search with errors and variable cost queries","volume":"68","author":"Sereno","year":"1998","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/j.ipl.2026.106640_bib0026","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1097\/00004032-197309000-00004","article-title":"Application of group testing procedures in radiological health","volume":"25","author":"Thomas","year":"1973","journal-title":"Health Phys."},{"key":"10.1016\/j.ipl.2026.106640_bib0027","unstructured":"P.D. Turney, Types of cost in inductive concept learning, arxiv:cs\/0212034 edition, 2002."},{"key":"10.1016\/j.ipl.2026.106640_bib0028","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.tcs.2024.114896","article-title":"Approximating decision trees with priority hypothesis","volume":"1023","author":"Yuan","year":"2025","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.ipl.2026.106640_bib0029","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0020-0190(94)90101-5","article-title":"Extending the quadrangle inequality to speed-up dynamic programming","volume":"49","author":"Borchers","year":"1994","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/j.ipl.2026.106640_bib0030","series-title":"Information Theory and Related Fields: Essays in Memory of Ning Cai","article-title":"Old and new results on alphabetic codes","volume":"14620","author":"Bruno","year":"2025"},{"issue":"10","key":"10.1016\/j.ipl.2026.106640_bib0031","doi-asserted-by":"crossref","first-page":"6974","DOI":"10.1109\/TIT.2024.3428699","article-title":"Bounds and algorithms for alphabetic codes and binary search trees","volume":"70","author":"Bruno","year":"2024","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10.1016\/j.ipl.2026.106640_bib0032","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1109\/18.79913","article-title":"Alphabetic codes revisited","volume":"37","author":"Yeung","year":"1991","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10.1016\/j.ipl.2026.106640_bib0033","doi-asserted-by":"crossref","first-page":"868","DOI":"10.1006\/jpdc.2000.1717","article-title":"The sound of silence: guessing games for saving energy in a mobile environment","volume":"61","author":"Dolev","year":"2001","journal-title":"J. Parallel Distrib. Comput."}],"container-title":["Information Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0020019026000219?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0020019026000219?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T04:10:52Z","timestamp":1780027852000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0020019026000219"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8]]},"references-count":33,"alternative-id":["S0020019026000219"],"URL":"https:\/\/doi.org\/10.1016\/j.ipl.2026.106640","relation":{},"ISSN":["0020-0190"],"issn-type":[{"value":"0020-0190","type":"print"}],"subject":[],"published":{"date-parts":[[2026,8]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Optimal average-case binary search with outcome-dependent costs","name":"articletitle","label":"Article Title"},{"value":"Information Processing Letters","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ipl.2026.106640","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"106640"}}