Using binary searches on workinglists in LANSA

Date:Archived
Product/Release:LANSA - All Platforms
Abstract:Binary searches are a quick method of finding particular values in a working list
Submitted By:LANSA Technical Support

When working lists exist that are large, it can become quite difficult to find particular values. A binary search can speed up the search significantly in such cases.

To use a binary search, a working list must be sorted. Binary searches work by halving the search list every time until the required value is found. The longer a working list, the more time a binary search will save you. This is because the relative number of GET_ENTRY commands is reduced in proportion to the number of entries to be searched. The table below shows an example of this:

Example

Here is RDML code which can be used to create a binary search :

FUNCTION OPTIONS(*DIRECT *NOMESSAGES *DEFERWRITE)
DEF_LIST NAME(#WORK1) FIELDS((#VALUE)) COUNTER(#LISTCOUNT) TYPE(*WORKING)
DEFINE FIELD(#VALUE) TYPE(*DEC) LENGTH(6) DECIMALS(2)
DEFINE FIELD(#SEARCH) TYPE(*DEC) LENGTH(6) DECIMALS(2)
DEFINE FIELD(#TOP) TYPE(*DEC) LENGTH(5) DECIMALS(0)
DEFINE FIELD(#BOTTOM) TYPE(*DEC) LENGTH(5) DECIMALS(0)
DEFINE FIELD(#INDEX) TYPE(*DEC) LENGTH(5) DECIMALS(0)

SORT_LIST NAMED(#WORK1) BY_FIELDS((#VALUE))
CHANGE FIELD(#BOTTOM) TO(1)
CHANGE FIELD(#TOP) TO(#LISTCOUNT)
DOWHILE COND('#BOTTOM *LT #TOP')
CHANGE FIELD(#INDEX) TO('#TOP + #BOTTOM / 2')
GET_ENTRY NUMBER(#INDEX) FROM_LIST(#WORK1)
CASE OF_FIELD(#VALUE)
WHEN VALUE_IS('*LT #SEARCH')
CHANGE FIELD(#BOTTOM) TO(#INDEX)
WHEN VALUE_IS('*GT #SEARCH)
CHANGE FIELD(#TOP) TO(#INDEX)
WHEN VALUE_IS('*EQ #SEARCH)
LEAVE
ENDCASE
ENDWHILE