Textbook errors in binary searching

ABSTRACT

This paper discusses the specification and implementation of binary searching. It begins by presenting a “standard” set of declarations, a specification, and a binary searching procedure written in Pascal. This procedure does not meet the specification: it contains five errors that also occur in many CS-1 and CS-2 textbooks. We will locate and study these errors, and show alternative procedures that correct them in a simple and understandable way.

Index Terms

• Social and professional topics

  • Professional topics

    • Computing education

      • Computing education programs

        • Computer science education

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language types

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

      • Sorting and searching