A Modified List Technique Allowing Binary Search

ABSTRACT

A modification of linked lists is presented which permits searching almost as efficiently as a pure binary search. The method depends on using consecutive memory locations for consecutive list elements whenever possible.

REFERENCES

• 1: Harry A. Clampett, Jr., Randomized binary searching with tree structures, Communications of the ACM, v.7 n.3, p.163-165, March 1964 [doi>10.1145/363958.363987]
• 2: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 3: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 4: W. A. Martin , D. N. Ness, Optimizing binary trees grown with a sorting algorithm, Communications of the ACM, v.15 n.2, p.88-93, Feb. 1972 [doi>10.1145/361254.361259]
• 5: Edward H. Sussenguth, Jr., Use of tree structures for processing files, Communications of the ACM, v.6 n.5, p.272-279, May 1963 [doi>10.1145/366552.366600]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Experimentation, Measurement, Performance, Theory