Browse Prior Art Database

Enhanced Binary Search

IP.com Disclosure Number: IPCOM000120186D
Original Publication Date: 1991-Mar-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 1 page(s) / 25K

Publishing Venue

IBM

Related People

Corr Jr, FP: AUTHOR

Abstract

Disclosed is an optimization of a pointer-based binary search on a sorted array of fixed length entries. The optimization is a simple method of computing the address of the middle entry (M) from the addresses of the lower (L) and upper (U) entries and the length of an entry.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 100% of the total text.

Enhanced Binary Search

      Disclosed is an optimization of a pointer-based binary search
on a sorted array of fixed length entries.  The optimization is a
simple method of computing the address of the middle entry (M) from
the addresses of the lower (L) and upper (U) entries and the length
of an entry.

      The address of the middle entry is given by either: (1)
M=(U+L)/2, if there is an odd number of entries between the upper and
lower entries, or (2) M=(U+L+length)/2, if there is an even number of
entries between the upper and lower entries.  The parity of the
number of entries between the upper and lower addresses is determined
by observing the bit in the addresses which corresponds to the least
significant set bit in the length.  If the addresses have the same
setting of this bit, then the number of entries between the upper and
lower entries is odd, otherwise it is even.

      Disclosed anonymously.