Browse Prior Art Database

Automatic Process for Retrieving Item from a List Using a Binary Technique

IP.com Disclosure Number: IPCOM000075782D
Original Publication Date: 1971-Nov-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 2 page(s) / 69K

Publishing Venue

IBM

Related People

Brewer, DE: AUTHOR

Abstract

BSTABLE is a routine for automatically building a table in a form that facilitates binary search. BSEARCH is a routine for retrieving an item from the table. One implementation of the process was based on the use of macro- instructions. This method has the advantage of programmer convenience for short tables. Other standard methods for generating reusable codes (e.g., subroutines or in-line code) would be preferred when execution speed and/or storage space are critical.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 79% of the total text.

Page 1 of 2

Automatic Process for Retrieving Item from a List Using a Binary Technique

BSTABLE is a routine for automatically building a table in a form that facilitates binary search. BSEARCH is a routine for retrieving an item from the table. One implementation of the process was based on the use of macro- instructions. This method has the advantage of programmer convenience for short tables. Other standard methods for generating reusable codes (e.g., subroutines or in-line code) would be preferred when execution speed and/or storage space are critical.

BSTABLE creates a binary search table consisting of an entry for each character string constant to be searched. An entry consists of: 1) one byte containing the relative length of the character string, 2) a pointer to the character string identity, 3) a pointer to the next lower entry in the binary tree, 4) a pointer to the next higher entry in the binary tree, 5) a one byte identifier that is associated with the character string, 6) the character string constant (always concatenated with its own identifier). The one byte identifier and character string constant combinations are referred to as "items" in the BSTABLE flow chart.

A few notes will help to explain the flow charts. At (1), a binary mapping table starts to be built. This table is used later to construct the binary search table. At
(2), the binary search table is begun. The first entry points to the node (top of the binary tree) and links to the next low (left bra...