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.

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)

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