bsearch.s

# Binary search (x86_64 GAS assmebler MacOS)
# returns index of `search` element or -1 for not found
#
# gcc bsearch.s -o bsearch && ./bsearch
# echo $?

.globl _main

.data
elements: .quad 1, 2, 3, 4, 5, 6, 7, 8
minindex: .quad 0
maxindex: .quad 7
search: .quad 3 # searching element
quadbytes: .quad 8

.text
_main:
    # r12 holds min index
    # r13 holds max index
    # r14 holds address of array
    # r15 holds real index

    mov minindex(%rip), %r12
    mov maxindex(%rip), %r13
    lea elements(%rip), %r14

body:
    # get difference between max and min
    mov %r13, %rax
    sub %r12, %rax

    # negative result -> element not found
    js notfound

    # get middle index
    mov $2, %rbx
    mov $0, %rdx
    div %rbx

    # store real index in r15
    mov %rax, %r15
    add %r12, %r15

    # get offset to middle element in array
    # offset in rax
    add %r12, %rax
    mulq quadbytes(%rip)

    # store middle element from array in rbx
    mov (%r14, %rax), %rbx

    # compare middle element from array with searching
    cmp search(%rip), %rbx

    # equals -> complete
    je complete

    # searching less -> go left
    ja left

    # searching greater -> go right
    jb right

left:
    sub $1, %r15
    mov %r15, %r13
    jmp body

right:
    add $1, %r15
    mov %r15, %r12
    jmp body

notfound:
    movq $-1, %rdi
    movq $0x2000001, %rax
    syscall

complete:
    movq %r15, %rdi
    movq $0x2000001, %rax
    syscall