Thursday, 3 April 2008

Linear Search

This short snippet of code performs a linear search on a sorted list. The average time to find a value in a sequence of x cells is x+3 cycles. This outperforms binary search on sequences up to 38 cells.

If the required values isn't in the sequence, a pointer to the first higher value is returned.
lsearch   slt    >ptr,           find
jmp _lsdone
djn lsearch, #length
jmp notfound

_lsdone sne find, <ptr
jmp found
jmp notfound

No comments: