US4674039A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for determining whether a given value is included in an ordered table of values stored in a computer readable memory
Assignee: Individual
•
Filing: 1984-10-09
•
Granted: 1987-06-16
•
Expires: 2004-10-09
Abstract
Abstract A method for operating a digital computer having computer readable memory means is used to determine whether a given value is included in an ordered table of values stored in the memory means. The method commences by defining lower and upper boundary positions and lower and upper boundary values. The lower and upper boundary positions are defined to be the first and last table positions, respectively, and the lower and upper boundary values are defined to be the values in the lower and upper boundary positions, respectively. An assumed position is then determined for the given value between the lower and upper boundary positions, and a test value is set equal to the value at the assumed position. The test value is then compared to the given value. If the test and given values are equal, then the given value is in the table at the assumed position. If the test value is greater than the given value, then the upper boundary position is adjusted towards the assumed position, the upper boundary value is redefined as the value at the adjusted upper boundary position, and the value of the lower boundary value is adjusted towards the given value. However, if the test value is less than the given value, then the lower boundary position is adjusted towards the assumed position, the lower boundary value is redefined as the value at the adjusted lower boundary position, and the value of the upper boundary value is adjusted towards the given value. The steps commencing with the determination of an assumed position for the given value are then repeated until the test value is equal to the given value, or until the upper and lower boundary positions are adjacent to one another. In a preferred embodiment, the assumed position is determined based upon the assumption that the values between the lower and upper boundary values change uniformly between the lower and upper boundary positions. The upper boundary position is preferably set equal to the assumed position when the test value is greater than the given value, and the lower boundary position is preferably set equal to the assumed position when the test value is less than the given value. The method of the present invention may also comprise the step of performing a binary search when a maxiumum repeat count has been equalled.
Inventors
- 👤 Farid A. Chouery
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 03:34
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90348; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99937
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
344 words
A method for operating a digital computer that includes computer memory means to determine whether a given value is included in an ordered table of values stored in the computer memory means and, if so, the position in the table at which the given value is included, the method comprising: (a) defining a lower boundary position as the first table position in the computer memory means and a lower boundary value as the value in the lower boundary position; (b) defining an upper boundary position as the last table position in the computer memory means and an upper boundary value as the value in the upper boundary position; (c) determining by interpolation an assumed position for the given value in the computer memory means between the lower and upper boundary positions; (d) comparing the value in the assumed position to the given value, and if they are equal, then causing the computer to indicate that the given value is in the table at the assumed position, and terminating the process; (e) when the value at the assumed position is greater than the given value, adjusting the upper boundary position towards the assumed position, redefining the upper boundary value as the value at the adjusted upper boundary position, and adjusting the value of the lower boundary value towards the given value by setting the lower boundary value equal to an average of the unadjusted lower boundary value and the given value; (f) when the value at the assumed position is less than the given value, adjusting the lower boundary position towards the assumed position, redefining the lower boundary value as the value at the adjusted lower boundary position, and adjusting the value of the upper boundary value towards the given value by setting the upper boundary value equal to an average of the unadjusted upper boundary value and the given value; and, (g) repeating the operations of steps (c)-(f) until the value in the assumed position is equal to the given value or until the upper and lower boundary positions are adjacent to one another.
Claim 2
Independent Claim
344 words
A method for operating a digital computer that includes computer memory means to determine whether a given value is included in an ordered table of values stored in the computer memory means and, if so, the position in the table at which the given value is included, the method comprising: (a) defining a lower boundary position as the first table position in the computer memory means and a lower boundary value as the value in the lower boundary position; (b) defining an upper boundary position as the last table position in the computer memory means and an upper boundary value as the value in the upper boundary position; (c) determining by interpolation an assumed position for the given value in the computer memory means between the lower and upper boundary positions; (d) comparing the value in the assumed position to the given value, and if they are equal, then causing the computer to indicate that the given value is in the table at the assumed position, and terminating the process; (e) when the value at the assumed position is greater than the given value, adjusting the upper boundary position towards the assumed position, redefining the upper boundary value as the value at the adjusted upper boundary position, and adjusting the value of the lower boundary value towards the given value by setting the lower boundary value equal to an average of the unadjusted lower boundary value and the given value; (f) when the value at the assumed position is less than the given value, adjusting the lower boundary position towards the assumed position, redefining the lower boundary value as the value at the adjusted lower boundary position, and adjusting the value of the upper boundary value towards the given value by setting the upper boundary value equal to an average of the unadjusted upper boundary value and the given value; and, (g) repeating the operations of steps (c)-(f) until the value in the assumed position is equal to the given value or until the upper and lower boundary positions are adjacent to one another.
Claim 3
Dependent Claim
38 words
The method of claim 1, wherein an assumed position is determined for the given value based upon the assumption that the values between the upper and lower boundary values change uniformly between the lower and upper boundary positions.
Claim 4
Dependent Claim
56 words
The method of claim 1, wherein the upper boundary position is set equal to the assumed position when the value at the assumed position is greater than the given value, and wherein the lower boundary position is set equal to the assumed position when the value at the assumed position is less than the given value.
Claim 5
Dependent Claim
77 words
The method of claim 1, comprising the further step of establishing a maximum repeat count prior to performing step (c) for the first time, and wherein step (g) comprises repeating the operations of steps (c)-(f) until the value in the assumed position is equal to the given value, until the upper and lower boundary positions are adjacent to one another, or until steps (c)-(f) have been repeated a number of times equal to the maximum repeat count.
Claim 6
Dependent Claim
35 words
The method of claim 4, comprising the further step of performing a binary search for the given value between the upper and lower boundary positions whenever the maximum repeat count is reached in step (g).
Claim 7
Dependent Claim
38 words
The method of claim 5, wherein the maximum repeat count is based upon the average number of iterations that would be required to determine that the given value is not in the table using a binary search technique.
Claim 8
Dependent Claim
31 words
The method of claim 6, wherein the maximum repeat count is proportional to the natural logorithm of the number of positions in the table divided by the natural logorithm of two.
Claim 9
Independent Claim
622 words
A method for operating a digital computer that includes computer memory means to determine whether a given value is included in an ordered table of values stored in the computer memory means and, if so, the position in the table at which the given value is included, the method comprising: (a) defining a lower boundary position as the first table position in the computer memory means and a lower boundary value as the value in the lower boundary position; (b) defining an upper boundary position as the last table position in the computer memory means and an upper boundary value as the value in the upper boundary position; (c) determining by interpolation an assumed position for the given value in the computer memory means between the lower and upper boundary positions; (d) comparing the value in the assumed position to the given value, proceeding to step (e) if they are equal, proceeding to step (f) if the value in the assumed position is greater than the given value, and proceeding to step (k) if the value in the assumed position is less than the given value; (e) causing the computer to indicate that the given value is in the table at the assumed position, and terminating the process; (f) adjusting the upper boundary position towards the assumed position, redefining the upper boundary value as the value at the adjusted upper boundary position, and adjusting the value of the lower boundary value towards the given value by setting the lower boundary value equal to an average of the unadjusted lower boundary value and the given value; (g) determining by interpolation an assumed position for the given value in the computer memory means between the lower and upper boundary positions; (h) comparing the value in the assumed position to the given value, proceeding to step (e) if they are equal, proceeding to step (f) if the value in the assumed position is greater than the given value, and proceeding to step (i) if the value in the assumed position is less than the given value; (i) comparing the upper and lower boundary positions, and proceeding to step (p) if they are adjacent to one another, and proceeding to step (j) if they are not adjacent to one another; (j) adjusting the lower boundary position towards the assumed position, redefining the lower boundary value as the value at the adjusted lower boundary position, and proceeding to step (c); (k) adjusting the lower boundary position towards the assumed position, redefining the lower boundary value as the value of the adjusted lower boundary position, and adjusting the value of the upper boundary value towards the given value by setting the upper boundary value equal to an average of the unadjusted upper boundary value and the given value; (l) determining by interpolation an assumed position for the given value in the computer memory means between the lower and upper boundary positions; (m) comparing the value in the assumed position to the given value, proceeding to step (e) if they are equal, proceeding to step (n) if the value in the assumed position is greater than the given value, and proceeding to step (k) if the value in the assumed position is less than the given value; (n) comparing the upper and lower boundary positions, and proceeding to step (p) if they are adjacent to one another, and proceeding to step (o) if they are not adjacent to one another; (o) adjusting the upper boundary position towards the assumed position, redefining the upper boundary value as the value of the adjusted upper boundary position, and proceeding to step (c); and (p) causing the computer to indicate that the given value is not in the table, and terminating the process.
Claim 10
Independent Claim
622 words
A method for operating a digital computer that includes computer memory means to determine whether a given value is included in an ordered table of values stored in the computer memory means and, if so, the position in the table at which the given value is included, the method comprising: (a) defining a lower boundary position as the first table position in the computer memory means and a lower boundary value as the value in the lower boundary position; (b) defining an upper boundary position as the last table position in the computer memory means and an upper boundary value as the value in the upper boundary position; (c) determining by interpolation an assumed position for the given value in the computer memory means between the lower and upper boundary positions; (d) comparing the value in the assumed position to the given value, proceeding to step (e) if they are equal, proceeding to step (f) if the value in the assumed position is greater than the given value, and proceeding to step (k) if the value in the assumed position is less than the given value; (e) causing the computer to indicate that the given value is in the table at the assumed position, and terminating the process; (f) adjusting the upper boundary position towards the assumed position, redefining the upper boundary value as the value at the adjusted upper boundary position, and adjusting the value of the lower boundary value towards the given value by setting the lower boundary value equal to an average of the unadjusted lower boundary value and the given value; (g) determining by interpolation an assumed position for the given value in the computer memory means between the lower and upper boundary positions; (h) comparing the value in the assumed position to the given value, proceeding to step (e) if they are equal, proceeding to step (f) if the value in the assumed position is greater than the given value, and proceeding to step (i) if the value in the assumed position is less than the given value; (i) comparing the upper and lower boundary positions, and proceeding to step (p) if they are adjacent to one another, and proceeding to step (j) if they are not adjacent to one another; (j) adjusting the lower boundary position towards the assumed position, redefining the lower boundary value as the value at the adjusted lower boundary position, and proceeding to step (c); (k) adjusting the lower boundary position towards the assumed position, redefining the lower boundary value as the value of the adjusted lower boundary position, and adjusting the value of the upper boundary value towards the given value by setting the upper boundary value equal to an average of the unadjusted upper boundary value and the given value; (l) determining by interpolation an assumed position for the given value in the computer memory means between the lower and upper boundary positions; (m) comparing the value in the assumed position to the given value, proceeding to step (e) if they are equal, proceeding to step (n) if the value in the assumed position is greater than the given value, and proceeding to step (k) if the value in the assumed position is less than the given value; (n) comparing the upper and lower boundary positions, and proceeding to step (p) if they are adjacent to one another, and proceeding to step (o) if they are not adjacent to one another; (o) adjusting the upper boundary position towards the assumed position, redefining the upper boundary value as the value of the adjusted upper boundary position, and proceeding to step (c); and (p) causing the computer to indicate that the given value is not in the table, and terminating the process.
Claim 11
Dependent Claim
44 words
The method of claim 8, wherein an assumed position is determined for the given value in steps (c), (g) and (l), based on the assumption that the values between the upper and lower boundary values change uniformly between the lower and upper boundary positions.
Claim 12
Dependent Claim
41 words
The method of claim 8, wherein in the upper boundary position is set equal to the assumed position in steps (f) and (o), and wherein the lower boundary position is set equal to the assumed position in steps (j) and (k).
Claim 13
Dependent Claim
106 words
The method of claim 8, comprising the further step of establishing a maximum repeat count prior to performing step (c) for the first time, wherein an iteration counter is incremented by one each time that a new assumed position is determined in step (c), (g) or (l), and wherein steps (i) and (n) include comparing the iteration counter to the maximum repeat count whenever the upper and lower boundary positions are not adjacent to one another, and performing a binary search for the given value between the upper and lower boundary positions whenever the iteration counter is greater than or equal to the maximum repeat count.
Claim 14
Dependent Claim
38 words
The method of claim 11, wherein the maximum repeat count is based upon the average number of iterations that would be required to determine that the given value is not in the table using a binary search technique.
Claim 15
Dependent Claim
31 words
The method of claim 12, wherein the maximum repeat count is proportional to the natural logorithm of the number of positions in the table divided by the natural logorithm of two.
References Cited (Backward Citations)
US2580768A
Cited
US2651457A
Cited
US3034720A
Cited
US3153775A
Cited
US3049295A
Cited
US3295102A
Cited
US3522589A
Cited
US3651483A
Cited
US3598973A
Cited
US3643226A
Cited
US3736413A
Cited
US4210961A
Cited
US4210961B1
Cited
US3890603A
Cited
US3781808A
Cited
US4241401A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1990-06-15 | 1990-12-15 | 1991-06-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1994-06-15 | 1994-12-15 | 1995-06-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1998-06-15 | 1998-12-15 | 1999-06-16 | $7700.00 | Window Closed / Lapsed |