Search

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.

Defining and Loading a Sample Array

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