Binary Search in Redcode

Binary search is an algorithm to find a value in a sorted list. Binary search finds the center element of the list and compares it to the target value.

If the target value is higher than the value of the center element, all elements below the center element can be eliminated from the search. Otherwise, all elements above the center element can be eliminated.

The search is then repeated on the remaining elements. In this way, binary search reduces the search space by 50% on each iteration. In Redcode, binary search is more efficient than linear search for lists of 38 or more elements.

The input parameters required are as follows:

• size - the number of elements
• bot - a pointer to the top of the sequence
• find - the target value to find

A pointer to the required element is returned in ptr.

          nop    <bot,           >size
_bsnext   mov.b  size,           ptr
          div    #2,             ptr
          jmn    _bscont,        ptr

          mov.b  bot,            ptr
          jmp    notfound,       >ptr

_bscont   add.b  bot,            ptr
          slt    @ptr,           find
          jmp    _bstopadj

          add.b  bot,            size
          sub.b  ptr,            size
          mov.b  ptr,            bot
          jmp    _bsnext

_bstopadj sne.b  @ptr,           find
          jmp    found

          div    #2,             size
          jmp    _bsnext