Search arrangement adapted for data range detection

Claim 2

A binary search arrangement for searching sequentially ordered data records of a data file, the data file defining a range of included data, the range being represented among the records by a record that is marked as a lower limit of the range and a separate record that is marked as an upper limit of the range, comprising; means for performing a binary search of the file for a predetermined datum, by examining the data records in a binary search sequence and for indicating completion of the binary search; means responsive to the indication of the completion of the binary search by the performing means, for examining the marking and the associated data of a last-examined one of the records to determine whether the last-examined one of the records examined by the performing means during the search is one of (a) marked as the lower range limit and lower in order than the predetermined datum, and (b) marked as the upper range limit and higher in the order than the predetermined datum; and means responsive to a determination by the determining means that one of (a) and (b) is true, for giving an indication that the predetermined datum is included in the file.

Claim 3

The arrangement of claim 1 wherein the record marked as the lower limit includes a first flag identifying this record; the record marked as the upper limit includes a second flag identifying this record; the performing means include means for comparing relative ordering of the predetermined datum with an examined data record; and the determining means include means for determining whether (c) the last-examined record includes the first flag and the comparing means indicate that the last-examined record is lower in the order than the predetermined datum, and means for determining whether (d) the last-examined record includes the second flag and the comparing means indicate that the last-examined record is higher in the order than the predetermined datum; and the indication-giving means include means for giving the indication when (c) or when (d) is true.

Claim 4

The arrangement of claim 1 wherein the performing means comprise memory means having addressable storage words each for storing one record of the file, each word having a first field for indicating whether the record is of the lower range limit and a second field for indicating whether the record is of the upper range limit, comparator means for determining relative ordering of the predetermined datum and the record stored by an addressed storage word of the memory, and generating one of (c) a first signal indicating that the compared record is lower in order than the predetermined datum and (d) a second signal indicating that the compared record is higher in order than the predetermined datum, and address-sequencer means responsive to results of comparisons performed by the comparator means, for addressing individual words of the memory in a binary-search sequence, and for generating a third signal to indicate completion of the binary search; the determining means comprise means for generating a fourth signal when either (e) the first field of an addressed word of the memory indicates that the stored record is of the lower range limit, when the first and the third signals are generated, or (f) the second field of an addressed word of the memory indicates that the stored record is of the upper range limit, when the second and the third signals are generated; and the indication-giving means give the indication when the fourth signal is generated.

Claim 5

The arrangement of claim 1 wherein: the data file further defines at least one individual datum represented among the records by its own individual record; the determining means include means responsive to the completion of the binary search for determining whether the last-examined one of the records (c) represents the predetermined datum; and the indication-giving means are responsive to a determination that one of (a), (b), and (c) is true, for giving an indication that the predetermined datum is included in the file.

Claim 6

The arrangement of claim 4 wherein: the indication-giving means are further responsive to a determination that (a), (b), and (c) are not true, for giving an indication that the predetermined datum is not included in the file.

Claim 7

The arrangement of claim 1 wherein: the data file defines a plurality of noncontiguous ranges of included data, each one of the ranges being represented among the records by a record of a lower limit of the range and a separate record of an upper limit of the range.

Claim 8

The arrangement of claim 1 wherein: the data file defines a plurality of ranges of included data, each said range being represented among the records by a record, dedicated exclusively to said range, of the lower limit of the range and a separate record, also dedicated exclusively to said range, of the upper limit of the range.

Claim 9

The arrangement of claim 7 wherein: the data file further defines at least one individual datum represented among the records by its own individual record; the determining means include means responsive to the completion of the binary search for determining whether the last-examined one of the records (c) represents the predetermined datum; and the indication-giving means are responsive to a determination that one of (a), (b), and (c) is true, for giving an indication that the predetermined datum is included in the file.

Claim 12

The method of claim 9 for searching the ordered date records wherein the record marked as the lower limit includes a first flag identifying this record, and the record marked as the upper limit includes a second flag identifying this record, the step of performing comprises the step of comparing relative ordering of the predetermined datum with an examined data record; the step of determining comprises the step of determining whether (c) the last-examined record includes the first flag and the last-examined record is determined to be comparatively lower in the order than the predetermined datum, or (d) the last-examined record includes the second flag and the last-examined record is determined to be comparatively higher in the order than the predetermined datum; and the step of giving an indication comprises the step of giving the indication when (c) or (d) is true.

Claim 13

The method of claim 9 for searching the ordered data records stored in a memory having addressable storage words each for storing one record of the file, each word having a first field for indicating whether the record is of the lower range limit and a second field for indicating whether the record is of the upper range limit, wherein: the step of performing comprises the steps of addressing individual words of the memory in a binary search sequence, comparing the predetermined datum with the record stored by an addressed storage word of the memory to determine their relative ordering, generating a first signal when the compared record is lower in order than the predetermined datum, generating a second signal when the compared record is higher in order than the predetermined datum, and generating a third signal when the binary search is completed; the step of determining comprises the steps of generating a fourth signal when the first field of an addressed word of the memory indicates that the stored record is of the lower range limit, when the first and the third signals are generated, and generating the fourth signal when the second field of an addressed word of the memory indicates that the stored record is of the upper range limit, when the second and the third signals are generated; and the step of giving an indication comprises the step of giving the indication when the fourth signal is generated.

Claim 14

The method of claim 9 for searching a data file further defining at least one individual included datum represented among the records by its own individual record, wherein: the step of determining includes the step of determining whether the last-examined one of the records (c) represents the predetermined datum, in response to the completion of the binary search; and the step of giving an indication comprises the step of giving an indication that the predetermined datum is included in the file, in response to a determination that one of (a), (b), and (c) is true.

Claim 15

The method of claim 12 further comprising the step of: giving an indication that the predetermined datum is not included in the file, in response to a determination that (a), (b), and (c) are not true.

Claim 16

The method of claim 9 for searching a data file defining a plurality of noncontiguous ranges of included data, each of the ranges being represented among the records by a record of a lower limit of the range and a separate record of an upper limit of the range.

Claim 17

The method of claim 9 for searching a data file defining a plurality of ranges of included data, each said range being represented among the records by a record, dedicated exclusively to said range, of the lower limit of the range and a separate record, also dedicated exclusively to said range, of the upper limit of the range.

Claim 18

The method of claim 15 for searching a data file further defining at least one individual included datum represented among the records by its own individual record, wherein: the step of determining includes the step of determining whether the last-examined one of the records (c) represents the predetermined datum, in response to the completion of the binary search; and the step of giving an indication comprises the step of giving an indication that the predetermined datum is included in the file, in response to a determination that one of (a), (b), and (c) is true.