Solution
.data
numbers: .word 28,37,44,60,85,99,121,127,129,138
.word 143,155,162,164,175,179,205,212,217,231
.word 235,238,242,248,250,258,283,286,305,311
.word 316,322,326,351,355,364,366,376,391,398
.word 408,410,415,418,425,437,441,452,474,488
.word 506,507,526,532,534,547,548,583,585,595
.word 603,621,640,661,666,690,692,713,719,750
.word 755,768,775,776,784,785,791,797,798,804
.word 828,842,846,858,884,887,890,893,908,936
.word 939,953,960,970,978,979,981,990,1002,1007
.text
.globl main
main: @ main function
stmfdsp!,{lr} @ save lr
ldr r0,=numbers @ pointer to array
ldr r1,=#418 @ key
mov r2,#0 @ start index
mov r3,#99 @ end index
mov r4,#0
stmfdsp!,{r4} @ pass num calls on the stack
blbinary_search @ call binary search
ldr r1, =0xFF200000 @ load ledr_base in r1
str r0,[r1,#0] @ save final value in ledr_base to display on leds
mov r0,#0 @ exit without error
ldmfdsp!,{lr} @ restore lr
movpc,lr @ return
@——————————————–
@ binary search routine
@ On entry:
@ r0 = address of numbers array
@ r1 = key
@ r2 = start index
@ r3 = end Index
@ [sp,#0] = num calls
binary_search:
stmfdsp!,{r4-r7,lr} @ save registers on the stack
sub sp,sp,#4 @ allocate space for a temporary variable
sub r5,r3,r2 @ calculate endindex-startindex
lsr r5,r5,#1 @ divide by 2
add r5,r5,r2 @ calculate middle: startindex + (endindex-startindex)/2
ldr r4,[sp,#24] @ load numcalls from stack
add r4,r4,#1 @ increment numcalls
if1:
cmp r2,r3 @ if startindex>endindex
ble if2
mov r0,#-1 @ return -1
b ret1
if2:
ldr r6,[r0,r5,lsl #2] @ load numbers[middleIndex] in r6
cmp r6,r1 @ if (numbers[middleindex]==key)
bne if3
mov r7,r5 @ keyindex= middleindex
b save1
if3:
cmp r6,r1 @ if (numbers[middleindex]>key)
ble else1
str r0,[sp,#0] @ save r0 in the stack
sub r3,r5,#1 @ set end index to middleIndex-1
stmfdsp!,{r4} @ pass num calls on the stack
blbinary_search @ recurse
mov r7,r0 @ keyindex = binary_search(numbers,key,start,middle-1,numcalls)
ldr r0,[sp,#0] @ load r0 from the stack
b save1
else1:
str r0,[sp,#0] @ save r0 in the stack
add r2,r5,#1 @ set start index to middleIndex+1
stmfdsp!,{r4} @ pass num calls on the stack
blbinary_search @ recurse
mov r7,r0 @ keyindex = binary_search(numbers,key,middle+1,end,numcalls)
ldr r0,[sp,#0] @ load r0 from the stack
save1:
mvn r4,r4 @ calculate -numCalls
add r4,r4,#1
str r4,[r0,r5,lsl #2] @ save numcalls: numbers[middleIndex]=-numCalls
mov r0,r7 @ return keyIndex
ret1:
add sp,sp,#4 @ remove temp variable from stack
ldmfdsp!,{r4-r7,lr} @ pop registers from the stack
add sp,sp,#4 @ remove passed argument from stack
movpc,lr @ return