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