Browse Prior Art Database

Pseudo Binary Search Technique

IP.com Disclosure Number: IPCOM000049511D
Original Publication Date: 1982-Jun-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 1 page(s) / 12K

Publishing Venue

IBM

Related People

Arndt, RL: AUTHOR

Abstract

The address offset to the approximate center of a table or portion of a table to be searched is computed by successively doubling a value initialized by the record length and comparing this value to the length of the table or portion thereof being searched. This technique may require one extra search when compared to a standard binary search technique, but an advantage of faster completion of the search is obtained.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 81% of the total text.

Page 1 of 1

Pseudo Binary Search Technique

The address offset to the approximate center of a table or portion of a table to be searched is computed by successively doubling a value initialized by the record length and comparing this value to the length of the table or portion thereof being searched. This technique may require one extra search when compared to a standard binary search technique, but an advantage of faster completion of the search is obtained.

In the previously utilized binary search technique a table size is divided by the record length to determine the number of records remaining to be searched. The number of records remaining to be searched is divided by two to find the center record of the table portion remaining to be searched. This center record relative number is multiplied by the record length to find the address offset of the center record. The offset is added to the top of the table pointer for addressing the center record. These multiplication and division operations take a relatively large amount of processor time or hardware to implement.

With the pseudo binary search technique, assume X is the record length and 43X is the table length. The address offset to the approximate center of this table is computed by doubling the record length X to obtain 2X. The 2X is saved and compared to 43X. Since 2X is less than 43X the 2X value is again doubled to 4X and the 4X is compared to 43X. Since 4X is less than 43X, the 4X is saved and the process of doublin...