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

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:

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