Should BTPFIND report end-of-tree?

Branches #5 showed how to modify the original BTPFIND routine so it did not return an insertion point at the end of a node, but instead called BTPSEQ to get the first position of the next node.

In that case, calling BTPFIND for a key greater than all keys in the tree makes BTPFIND return a null id. For example, if the highest ZIP code in a B-tree is 99998, then calling BTPFIND to find 99999 would return a null id (indicating the search "went off the end of the tree"). For some applications, that might be useful information, but for other programs such as browsers, that might create an invalid situation that leaves the operator with nothing to look at. (After all, after searching for 99999, shouldn't the browser just stop at the last possible key and display that one instead?)

If you want BTPFIND to return a null id after searches beyond the end of the tree, the code from Branches #5 will suffice. But if you want BTPFIND to instead return the last item id, use:

 SUBROUTINE BTPFIND(ROOT,BFILE,DFILE,ID,ITEM,NODE.ID,NODE.POS)
 CALL BTPKEY(ROOT, ID, ITEM, FK)
 READ NODE.ID FROM BFILE, ROOT ELSE STOP "BTP8"
 100 READ N FROM BFILE, NODE.ID ELSE STOP "BTP9"
 L = 0 ; R = N<1>+1
 IF R = 1 THEN NODE.POS = 1 ELSE
   LOOP
     NODE.POS = INT((L+R)/2)
     UID = N<2, NODE.POS>
     IF UID = ID THEN RETURN
     READ IT FROM DFILE, UID ELSE STOP "BTP10"
     CALL BTPKEY(ROOT, UID, IT, KEY)
     IG = (FK > KEY)
     IF IG THEN L = NODE.POS ELSE R = NODE.POS
   UNTIL (R-L) <= 1 DO REPEAT
   IF IG THEN NODE.POS = R
   END
 NNID = N<3, NODE.POS>
 IF NNID # "" THEN
   NODE.ID = NNID
   GO TO 100
   END
 IF NODE.POS > N<1> THEN ;* want next node
   NODE.POS = N<1> ;* go to end of current node
   LAST.NODE.ID = NODE.ID ;* in case BTPSEQ fails
   CALL BTPSEQ(BFILE,NODE.ID,NODE.POS,"NEXT",ID)
   IF ID = "" THEN ;* beyond end of tree
     NODE.POS = N<1> ;* go to end of last node
     ID = N<2,NODE.POS> ;* extract the key
     NODE.ID = LAST.NODE.ID ;* recover the node id
     END
   RETURN
   END
 ID = N<2, NODE.POS>
 RETURN
 END