binary_search.asm

%include "asm_io.inc"

segment .data
	prompt1	db	"Array length: ", 0
	prompt2	db	"Array elements (space separated):", 0
	prompt3	db	"Looking for ", 0
segment .bss
	len	resd	1
	lookup_val	resb	1
	arr_p	resd	1
segment .text
	global	_asm_main
	extern	malloc, free
_asm_main:
	enter	0, 0
	pusha
	
	mov	eax, prompt1	
	call	print_string

	call	read_int
	mov	[len], eax

;	Prints out the user-given array length 	
;	mov	eax, [len]	
;	call	print_int
	
	xor	eax,	eax
	push	dword [len]
	call	malloc		;eax is now pointer to array
	add	esp, 4
	mov	[arr_p], eax

;	Prints out Address of arr (stored at [arr_p]
	mov	eax, [arr_p]
	call	print_int
	call	print_nl
	
	mov	eax, prompt2
	call	print_string

	mov	edx, [arr_p]	;edx = running pointer to current array element
	xor	ecx, ecx	;ecx = 0 (counter)
read_char_loop:
	cmp	ecx, [len]
	jge	end_char_loop	;end if ecx >= len

	call	read_int
	mov	byte [edx], al	;move bottom byte of eax to arr[edx]
	inc	edx
	inc	ecx
	jmp	read_char_loop
end_char_loop:
	mov	eax, prompt3
	call	print_string
	
	
	call	read_int
	mov	[lookup_val], eax

	;Prints Address of arr (stored at [arr_p]) -> DIFFERENT FROM LINE 35! 
	mov	eax, [arr_p]
	call	print_int
	call	print_nl

	push	dword [lookup_val]
	push	dword [len]
	push	dword [arr_p]
	call	binary_search
	add	esp, 12
	
	call	print_int
	
        push  dword [arr_p]
        call  free
        add  esp, 4
	

	popa
	leave
	mov	eax, 0
	ret


;int binary_search(int[] arr, int len, int el) {
;	int l = 0;
;	int r = len-1;
;	//2
;	if(l > r) {
;		return -1;
;	}
;
;	
;	int m = floor((L+R) / 2);
;	if (arr[m] < el) {
;		l = m + 1;
;		jmp 2;
;	}
;	if (arr[m] > el) {
;		r = m - 1;
;		jmp 2;
;	}
;	
;	return m;
;}
;example: searching 4
; [ 0, 4, 6, 7, 10 ]       [ 0, 4, 6, 7, 10 ]       [ 0, 4, 6, 7, 10 ]
;   ^-----^-----^     ==>    ^--^              ==>       ^
;   l     m     r           l,m r                      l,m,r
binary_search:
	enter	4, 0		;m as local variable
	pusha

	dump_mem	0, [ebp+8], 2
	dump_stack	1, 2, 4	
	dump_regs	2
	xor	eax, eax	;eax = l = 0
	mov	ebx, [ebp + 12]	;ebx = r = len-1
	dec	ebx

iter:
	cmp	eax, ebx
	jg	not_found

	mov	ecx, eax
	add	ecx, ebx	 
	shr	ecx, 1		;ecx = floor((l+r) / 2)

	mov	[ebp - 4], ecx	;m = ecx
	
	mov	edx, [ebp + 8]	;edx = array start address
	add	edx, [ebp - 4]	;edx = address to arr[m] 
	mov	edx, [edx]	
	and	edx, 255	;clear top 3 bytes of edx 

	cmp	edx, [ebp + 16]	
	jl	overshoot 
	jg	undershoot

	popa	
	mov	eax, [ebp - 4]
	jmp	end_func	;arr[m] == el
	
overshoot:
	mov	eax, [ebp - 4]
	inc	eax
	jmp	iter

undershoot:
	mov	ebx, [ebp - 4]
	dec	ebx
	jmp 	iter

not_found:
	popa
	mov	eax, 1
	neg	eax

end_func:
	leave
	ret