Binary searches: Was: Access Key for a Sub File ? -- MIDRANGE-L

I remember having to write a binary search for just about every computer
class I took in college way back when before colleges had computer related
degrees.  And I thought beer drinking was the ONLY useful skill I learned
back then!
Carl
Carl Galgano
EDI Consulting Services, Inc.
540 Powder Springs Street
Suite C19
Marietta, GA  30064
770-422-2995
mailto: cgalgano@ediconsulting.com
http://www.ediconsulting.com
EDI, Communications and AS400 Technical Consulting

-----Original Message-----
From: James W Kilgore <email@james-w-kilgore.com>
To: MIDRANGE-L@midrange.com <MIDRANGE-L@midrange.com>
Date: Thursday, February 18, 1999 12:33 PM
Subject: Re: Access Key for a Sub File ?


>Sounds like a natural for RRN halving.
>
>If you've not done this before, here's a quick review:
>1) As you load the subfile, save low voucher value.
>2) As you load the subfile, save high voucher value and last RRN
>written.
>3) When receiving a "position to" request, validate that it is within
>low/high range.
>4) Initialize working low/high RRN. (low=1, high=last written)
>5) CHAIN subfile record at ((highRRN-lowRRN)+1)/2
>6a) If retrieved voucher value is less than requested voucher, set
>lowRRN to current RRN.  (You want the second half of the file)
>6b) Else set highRRN to current RRN (You want the first half of the
>file)
>6c) Go to step 5
>
>We get out of this loop when retrieved value matches requested value or
>when the highRRN-lowRRN is <= page size. In the latter case we start a
>record by record loop/compare as originally suggested.
>
>If the user will be doing a lot of positioning, you may want to get the
>25/50/75% values right after loading the subfile and eliminate 2 CHAIN
>operations with each positioning by doing a simple compare instead and
>then set lowRRN and highRRN accordingly.
>
>As you see, half of the file is eliminated with the first CHAIN, half of
>the remaining half is eliminated with the second CHAIN.  Each CHAIN
>eliminates half of the remaining file record range.
>
>Give it a try, I think you'll be pleased with the response time.
>
>James W. Kilgore
>email@James-W-Kilgore.com
>
>P.S. BTW this can also be used to speed up LOKUP operations on an
>ordered array.
>
>
>
>
>Adhip C Lahiri wrote:
>>
>> Folks,
>>         I have a fairly complicated code that amongst other things
>> has  a one-shot build subfile which also has a subfile field called
Voucher.
>> I need to implement a new "position to"  using a  Starting Voucher search
>> field in the control.
>+---
>| This is the Midrange System Mailing List!
>| To submit a new message, send your mail to MIDRANGE-L@midrange.com.
>| To subscribe to this list send email to MIDRANGE-L-SUB@midrange.com.
>| To unsubscribe from this list send email to
MIDRANGE-L-UNSUB@midrange.com.
>| Questions should be directed to the list owner/operator:
david@midrange.com
>+---

BEGIN:VCARD
VERSION:2.1
N:Galgano;Carl;J.
FN:Carl J. Galgano
ORG:EDI Consulting Services, Inc.
TEL;WORK;VOICE:770-422-2995
TEL;PAGER;VOICE:770-839-8168
TEL;WORK;FAX:770-425-8391
ADR;WORK;ENCODING=QUOTED-PRINTABLE:;;540 Powder Springs Street=0D=0ASuite C19;Marietta;GA;30064
LABEL;WORK;ENCODING=QUOTED-PRINTABLE:540 Powder Springs Street=0D=0ASuite C19=0D=0AMarietta, GA 30064
URL:
URL:http://www.ediconsulting.com
EMAIL;PREF;INTERNET:cgalgano@ediconsulting.com
REV:19990219T023245Z
END:VCARD