The Museum of HP Calculators

Binary Search Subroutine for the HP-41C

This program was witten by Ed Eriksen and is used here by permission.

This program is supplied without representation or warranty of any kind. The author and The Museum of HP Calculators therefore assume no responsibility and shall have no liability, consequential or otherwise, of any kind arising from the use of this program material or any part thereof.

Overview

This function is intended to be used in another function. It will locate and return the register number where a target value is stored.

The subroutine is geared to an array of registers, each of which contain a key.value combination, where the integer component of the stored value is a key, and the decimal component is an associated value. This type of array is similar to an 'associative array' in modern day Perl. It is based on the concept of maximizing register use by storing two values in each register.

An example of an HP41CV 'associative array' would be a series of check numbers and related amounts, with each check/amount combination stored as a single decimal number (check.amount, where the amount has been divided by 10,000 and added to the check number). In this storage configuration, the BSCH routine could be used to identify the register number where a check/amount combination is stored, using the check number as a search key.

To modify for use with a search key expected to completely match a value stored in the search range, see Adaptations below.

This routine is substantially faster than a sequential search intended to accomplish the same purpose.

Assumptions

The search range consists of registers in contiguous order.
Stored values are sorted in ascending sequence across the search range.
Stored values are unique across the search range.

Required Parameters on Entry

Stack Register Y: The lowest register of the search range .
Stack register X: The highest register of search range.
Register 00: The value to be searched for (must be an integer).

Values at exit

Stack register X: Register number where the search key was found. If the search key wasn't found, this value will be 0.00
Register 00: The complete value (integer and decimal) contained in the returned register. If the search key wasn't found, this value will be that of the search key.

Known Bugs
No bugs have been identified when this routine is used correctly. If a decimal value is used as the search key, however, the program will loop indefinitely.
Adaptations
With modification, the subroutine can be used to search an array of registers to find a stored value that is exactly equal to the full search key. In this storage configuration, each register contains a single value instead of a key.value combination.
Alter the original subroutine as follows: Delete step 18 (INT). This step originally stripped the decimal component of a stored key.value combination prior to comparison with the search key. Delete step 36 (LASTX). This step originally retrieved the full value contained in the register where the search key was found. It is not necessary if the search key and matching value are identical. Delete step 37 (STO 00). This step originally stored the full value retrieved in the previous step. Modify step 38 (RCL T). Substitute RCL Z. Since steps 36 and 37 are no longer present, the register number where the search key was found is one level lower in the stack.

Instructions

Step

Instructions

Input Data/Units

Keys

Output Data/Units

1

Enter subprogram

2

Save value to find in R00

search value

STO 00

3
Key in lowest register to search
low

ENTER

4
Key in highest register to search and begin
high

XEQ BSCH

register # or 0.00
(plus value in R00)

The Program

LINE  KEYS
 01 LBL "BSCH"
 02   FIX 0
 03   STO 02
 04   RDN
 05   STO 01
 06 LBL 01
 07   RCL 02
 08   RCL 02
 09   RCL 01
 10   -
 11   2
 12   /
 13   RND
 14   X<0?
 15   ENTER 
 16   -
 17   RCL IND X
 18   INT
 19   RCL 00
 20   X=Y?
 21   GTO 03
 22   X>Y?
 23   GTO 02
 24   RCL Z
 25   1
 26   -
 27   STO 02
 28   GTO 01
 29 LBL 02
 30   RCL Z
 31   1
 32   +
 33   STO 01
 34   GTO 01
 35 LBL 03
 36   LASTX
 37   STO 00
 38   RCL T
 39   FIX 2
 40   END

Register Use

R00  Target Value
R01  Lowest register number to search
R02  Highest register number to search

Go back to the HP-41 software library
Go back to the general software library
Go back to the main exhibit hall

Step	Instructions	Input Data/Units	Keys	Output Data/Units
1	Enter subprogram
2	Save value to find in R00	search value	STO 00
3	Key in lowest register to search	low	ENTER
4	Key in highest register to search and begin	high	XEQ BSCH	register # or 0.00 (plus value in R00)