Binary search—think positive

Reference. Binary search—think positive

Alexander Dinges, Ralf Hinze · JFP · 2025 · program-calculation · DOI · pldb

Cite

Cite as @dinges-2025-binary (helia, typst) · \cite{dinges-2025-binary} (LaTeX)

BibTeX

bibtex · 1 line

@article{dinges-2025-binary, title={Binary search—think positive}, volume={35}, ISSN={1469-7653}, url={http://dx.doi.org/10.1017/s0956796825000061}, DOI={10.1017/s0956796825000061}, journal={Journal of Functional Programming}, publisher={Cambridge University Press (CUP)}, author={DINGES, ALEXANDER and HINZE, RALF}, year={2025} }

hayagriva YAML (typst)

yaml · 16 lines

dinges-2025-binary:
  type: article
  title: Binary search—think positive
  author:
  - DINGES, ALEXANDER
  - HINZE, RALF
  date: 2025
  url: http://dx.doi.org/10.1017/s0956796825000061
  serial-number:
    doi: 10.1017/s0956796825000061
    issn: 1469-7653
  parent:
    type: periodical
    title: Journal of Functional Programming
    publisher: Cambridge University Press (CUP)
    volume: 35

Download: dinges-2025-binary.bib · dinges-2025-binary.yml

Cited by (1)

Truly Functional Solutions to the Longest Uptrend Problem (Functional Pearl) dinges-2025-trulyICFP · 2025

Solutions to the longest increasing subsequence problem are typically implemented imperatively, relying on arrays for constant-time lookups and updates. Replacing these arrays with functional sequences allows a purely functional solution with the same asymptotic running time, but with significantly worse practical performance. In this pearl, we present a purely functional approach that is not only asymptotically optimal, but also efficient in practice. The core idea is to exploit the interplay between search, lookup, and update operations through Huet’s zipper. In addition, we improve the adaptive behaviour of imperative solutions commonly found in the literature.

PDF · DOI · pldb

Cites 5 works (0 here)

External (5)

Extra, extra — read all about it: Nearly all binary searches and mergesorts are broken (2006)
Programming: The Derivation of Algorithms (1990)
Introduction to Functional Programming (1988)
Why numbering should start at zero (1982)
The Art of Computer Programming, Volume 3: Sorting and Searching (1973)