Our first step is to define a set, S1, and give it the attribute X using the following sets section:

SETS:

 S1: X;

ENDSETS

The X attribute will store the list that we will search for the key value.  We populate X and input our key in the data section:

DATA:

! The key for which we will search;

 KEY = 16;

! The list (must be in sorted

  increasing order);

 X = 2 7 8 11 16 20 22 32;

ENDDATA

Note that for the purposes of this example, the list of values must be input in sorted order.  An interesting exercise would be to extend this model so that it tests to determine if the data is sorted.  Or, if you are really ambitious, extend the model so that it will sort a list with arbitrary ordering.

Next comes the calc section, which contains our code to do the binary search.  In the first part of the calc section:

CALC:

! Set begin and end points of search;

 IB = 1;

 IE = @SIZE( S1);

we bracket the key by pointing to the beginning of the list, IB, and the end of the list, IE.  Note that we make use of the @SIZE function to dynamically compute the size of the list.

Next, we have the @WHILE loop to search for the key value:

! Loop to find key;

 @WHILE( IB #LE# IE:

  ! Cut bracket in half;

   LOC = @FLOOR((IB + IE)/2);

   @IFC( KEY #EQ# X(LOC):

     @BREAK; ! Do no more loops;

   @ELSE

     @IFC( KEY #LT# X( LOC):

       IE = LOC-1;

     @ELSE

       IB = LOC+1;

     );

   );

 );

The @WHILE loop tests if the candidate range has become empty at the start of each iteration:

@WHILE( IB #LE# IE:

If not, we continue by dissecting the bracket in half:

!cut bracket in half;

INEW = @FLOOR( ( IE + IB) / 2);

We then determine if the new bracket point resides above or below the key and set IB and IE accordingly:

@IFC( KEY #EQ# X(LOC):

  @BREAK; ! Do no more loops;

@ELSE

  @IFC( KEY #LT# X( LOC):

    IE = LOC-1;

  @ELSE

    IB = LOC+1;

  );

);

Finally, when we fall out of the @WHILE loop we display the result of our search:

 @IFC( IB #LE# IE:

  ! Display key's location;

   @PAUSE( 'Key is at position: ', LOC);

 @ELSE

  ! Key not in list;

   @STOP( ' Key not on list!!!');

 );

If the eligible range is empty, then we did not find the key.  Otherwise, the key was found and report its location on the list.

If you run this model, LINGO should successfully find the key and display: