(27S, 17BII, 19BII) Binary search (high/low) assistant

[Dave Britten]

This small solver "program" assists you in performing a manual binary search for some unknown value between known initial lower and upper bounds.

Usage:

Store the initial lower bound in [L], the initial upper bound in [H], and solve for [GO]. The first value you should test will be on the display. If your target value is higher than this test value, solve for [UP]. If the target value is lower, solve for [DN]. Repeat solving for [UP] or [DN] until the target value has been identified.

Example:

Suppose you're using some data processing program, and you've discovered a bug. The program fails when the input data set is larger than some unknown amount, meaning you'll have to break up the processing into batches if you need to process more than that amount. However, because processing a small number of large batches will be faster than a large number of small batches, you want to configure it to process the largest batches possible. You know that the program works fine when the input data is 1 record, and fails when the input data is 200,000 records. The goal is to determine exactly where in that range the failure point lies.

Set up the example:

1 [L]
200000 [H]
[GO]

...and see 100,000 in the display. You test your program with 100,000 input records. The program runs correctly, so the failure point is higher than 100,000.

Solve for [UP], and see 150,001. You test the program with this number of records. The program fails, so the failure point is lower than 150,001. Solve for [DN], and see 125,000. Keep solving for [UP] or [DN] and retesting the program until you find the failure point:

[UP] UP=137,501
[DN] DN=131,250
[DN] DN=128,125
[UP] UP=129,688
[UP] UP=130,469
[UP] UP=130,860
[UP] UP=131,055
[UP] UP=131,153
[DN] DN=131,103
[DN] DN=131,079
[DN] DN=131,067
[UP] UP=131,073
[DN] DN=131,070
[UP] UP=131,072
[DN] DN=131,070
[UP] UP=131,071

Thus you determine that the program works with 131,070 records, and fails with 131,071.

Code:

BSEARCH:
0*IF(
    S(UP):
    0
    *L(C:-1)
    *L(
        L:
        -INT(-(G(H)+G(L))/2)
    ):
    0
    *L(C:1)
    *IF(
        S(DN):
        L(H:INT((G(L)+G(H))/2)):
        0
    )
)
+INT(G(C)*(L+H)/2)*G(C)
=IF(S(UP):UP:IF(S(DN):DN:GO))