SQR Techniques - Searching Arrays
 Two forms of binary searches are demonstrated along with the standard linear search. To successfully utilize a binary search the table must be sorted.

 We'll load a simple 1000 element array with a key value ranging from '0001' to '1000' (ascending order). The objective of each search routine is to find the search key in the array. Please note once the array is loaded the greatest power of 2 less than or equal to the element count is calculated. The first binary search method uses this as the search start point. In our example the start point will be element# 512 (2**9) since we have 1000 elements in our table.
 ```!********************************************************************** !* Define Array * !********************************************************************** begin-procedure Define-Array create-array name=ARRdat size=1001 field=ARRkey:char let #ARR = 0 let #ARR_max = 1000 end-procedure !********************************************************************** !* Load Array * !********************************************************************** begin-procedure Load-Array let #ARR = 0 while #ARR < #ARR_max let #ARRkey = #ARR + 1 let \$ARRkey = edit(#ARRkey,'0999') let ARRdat.ARRkey (#ARR) = \$ARRkey let #ARR = #ARR + 1 end-while let #ARRb = 1 while #ARRb <= #ARR ! Determine minimum power of 2 let #ARRb = #ARRb * 2 ! greater than entry count end-while if #ARRb > 1 let #ARRb = #ARRb / 2 ! Set Binary Search Start Point end-if display ' ' display ' Total Entries: ' noline display #ARR 999 display 'Binary Search Start: ' noline display #ARRb 999 display ' ' end-procedure ```

 Binary Search
 ```!********************************************************************** !* Binary Search * !********************************************************************** begin-procedure SRCH-Binary let #ctr = 0 let #ARRs = #ARRb let #ARRl = #ARRb let \$ARRsw = 'N' while #ARR > 0 if \$ARRsw = 'Y' or #ARRs > #ARR or #ARRl < 1 break end-if let #ARRg = #ARRs - 1 let #ARRl = #ARRl / 2 let \$ARRkey = ARRdat.ARRkey (#ARRg) let #ctr = #ctr + 1 evaluate \$ARRkey when = \$SRCHkey let \$ARRsw = 'Y' when > \$SRCHkey let #ARRs = #ARRs - #ARRl when < \$SRCHkey let #ARRs = #ARRs + #ARRl while #ARRs > #ARR and #ARRl > 1 let #ARRl = #ARRl / 2 let #ARRs = #ARRs - #ARRl end-while end-evaluate end-while end-procedure ```

 Binary Search - Alternate Method
 ```!********************************************************************** !* Alternate Search * !********************************************************************** begin-procedure SRCH-Alternate let \$ARRsw = 'N' let #ctr = 0 let #IDXh = #ARR - 1 let #IDXl = 0 while #IDXl <= #IDXh let #idx = trunc(((#IDXl + #IDXh)/2),0) let \$ARRkey = ARRdat.ARRkey (#idx) let #ctr = #ctr + 1 evaluate \$ARRkey when = \$SRCHkey let #IDXl = #IDXh + 1 let \$ARRsw = 'Y' when > \$SRCHkey let #IDXh = #idx - 1 when < \$SRCHkey let #IDXl = #idx + 1 end-evaluate end-while end-procedure ```

 Linear Search (Sequential)
 ```!********************************************************************** !* Sequential Search * !********************************************************************** begin-procedure SRCH-Sequential let \$ARRsw = 'N' let #idx = 0 let #ctr = 0 while #idx < #ARR_max let \$ARRkey = ARRdat.ARRkey (#idx) let #ctr = #ctr + 1 if \$SRCHkey = \$ARRkey let \$ARRsw = 'Y' break end-if if \$SRCHkey < \$ARRkey break end-if let #idx = #idx + 1 end-while end-procedure ```

 Feedback
 I would appreciate any feedback you may have on this site. Send mail to tdelia@erols.com or click on the Octopus.
 Technical difficulties?
 Please report any technical difficulties you may encounter to the address above OR click on the Octopus. Thanks.

Tony DeLia  -  Updated April 28, 1999