6502.org • View topic - Binary search implementation

View unanswered posts | View active topics

Board index » 6502.org Users Forum » Programming

All times are UTC

Binary search implementation

Page 1 of 1

[ 4 posts ]

Previous topic | Next topic

Author

Message

atolle

Post subject: Binary search implementation

Posted: Tue Aug 07, 2007 4:35 am

Joined: Mon Aug 06, 2007 1:42 pm
Posts: 5

Just wanted to share something I put together for a project of mine. I've been using it for some time, so it has been tested.

A binary search is an amazingly efficient search algorithm for large, pre-sorted tables of data. The maximum number of iterations is 1+log<base2>N, meaning that searching a full table of 32,768 unique values would take a maximum of 12 comparisons (or would it be 11... I don't know how to round logarithms :).

The code I use in production actually searches for data referenced by a table of pointers, so there is one more level of indirection than in the code presented below.

Feel free to tear apart my coding... I love to find out better ways of doing things.

The source is formatted for the ACME cross-compiler.

Code:

; BINSRCH
; searches sorted table of 16-bit values (table must be aligned
;     on two-byte boundary).

; prior to entry,
;     .low should point to first entry in the table.
;     .high should point to last entry in the table.
;     .value should contain the search target.

; on exit,
;     if carry set, value was found, and .mid contains pointer.
;     if carry clear, value not found, and .low points to where
;          target value should be inserted.


; zero page pointers

.low      = $10
.high     = $12
.mid      = $14
.value    = $16
.size     = 2                      ; element size (must be power of 2)


BINSRCH

.loop
          SEC                      ; calculate high - low
          LDA .high
          SBC .low
          TAX                      ; preserve LSB of difference in X
          LDA .high+1
          SBC .low+1
          BCC .done                ; if low > high, not found
          LSR                      ; calculate (high - low) / 2
          TAY
          TXA
          ROR                      ; carry cleared because multiple of 2
          AND #$100 - .size        ; align to element size
          ADC .low                 ; mid = low + ((high - low) / 2)
          STA .mid
          TYA
          ADC .low+1
          STA .mid+1
          LDA .value+1             ; load target value MSB
          LDY #1                   ; load index to MSB
          CMP (.mid),Y             ; compare MSB
          BEQ .chklsb
          BCC .modhigh             ; A[mid] > value
.modlow                            ; A[mid] < value
          LDA .mid                 ; low = mid + element size
          ADC #.size - 1           ; carry always set
          STA .low
          LDA .mid+1
          ADC #0
          STA .low+1
          JMP .loop
.chklsb
          LDA .value               ; load target value LSB
          DEY                      ; set index to LSB
          CMP (.mid),Y             ; compare LSB
          BEQ .done
          BCS .modlow              ; A[mid] < value
.modhigh                           ; A[mid] > value
          LDA .mid                 ; high = mid - element size
          SBC #.size - 1           ; carry always clear
          STA .high
          LDA .mid+1
          SBC #0
          STA .high+1
          JMP .loop
.done
          RTS

Top

bogax

Post subject: Re: Binary search implementation

Posted: Fri Aug 10, 2007 8:02 am

Joined: Tue Nov 18, 2003 8:41 pm
Posts: 250

atolle wrote:

A binary search is an amazingly efficient search algorithm for large, pre-sorted tables of data. The maximum number of iterations is 1+log<base2>N, meaning that searching a full table of 32,768 unique values would take a maximum of 12 comparisons (or would it be 11... I don't know how to round logarithms

log 32768 to the base 2 is 15

32768 two byte pointers doesn't leave much room for code

Seems like you're making an extra pass that you don't need.

Top

atolle

Post subject: Re: Binary search implementation

Posted: Sat Aug 11, 2007 1:57 pm

Joined: Mon Aug 06, 2007 1:42 pm
Posts: 5

bogax wrote:

log 32768 to the base 2 is 15

Silly me... I was calculating the natural logarithm.

bogax wrote:

32768 two byte pointers doesn't leave much room for code ;)

True :)

bogax wrote:

Seems like you're making an extra pass that you don't need.

Yeah, this is the version of the algorithm that tests for equality during the search. I decided to go with it because the termination test, "if low > high", can be checked with a simple BCC after calculating the difference. The test in the early termination version, "if low >= high", means extra code to test if low and high are equal. Perhaps there is a quick way to do that while also computing the difference.

In the code where I use this routine, I need to know if the target value was found, so it works out anyway. The early termination version would need an additional post-termination test to see if the target value was found.

Top

kc5tja

Post subject: Re: Binary search implementation

Posted: Sat Aug 11, 2007 4:05 pm

Joined: Sat Jan 04, 2003 10:03 pm
Posts: 1706

atolle wrote:

The test in the early termination version, "if low >= high", means extra code to test if low and high are equal. Perhaps there is a quick way to do that while also computing the difference.

When computing the difference, the Z flag will be set if they're equal. However, to exploit this, you'll need to BNE inside the subtraction code after doing the low byte, since the next LDA will invariably alter the Z flag.

Top

Page 1 of 1

[ 4 posts ]

Board index » 6502.org Users Forum » Programming

All times are UTC

Who is online

Users browsing this forum: No registered users and 3 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum