Monday, 28 April 2008

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

No comments: