The following high-level language procedure recursively performs a binary search
ID: 3727618 • Letter: T
Question
The following high-level language procedure recursively performs a binary search for a key within an array of sorted (ascending) integers. Translate this procedure into MIPS code. Write a main procedure to dynamically allocate an array of n integers (n is a user input that must be greater than 1), read an array of n sorted (ascending) integers, print the array of n sorted integers, print the index of the matching element if the key is found, otherwise print the value -(index where the key can be inserted). You need to write procedures for reading and printing the array, and pass parameters properly a MIPS convention. ccording to the Search sortedArray[first]..sortedArray[last] for key. index of the matching element if it finds key, otherwise - (index where it could be inserted) sortedArray: array of sorted (ascending) integers first, last: lower and upper subscript bounds. integer to search for. // procedure // returns: // parameters: // key: int BinarySearch (int sortedArray[], int first, int last, int key) f if (first last) { int mid = (first + 1ast) / 2; // compute mid point. if (key sortedArray[mid]) return mid; return BinarySearch(sortedArray, first, mid-1, key); return BinarySearch(sortedArray, mid+1, last, key); else if (keyExplanation / Answer
.file 1 "" .section .mdebug.abi32 .previous .nan legacy .module fp=32 .module nooddspreg .abicalls .text .align 2 .globl binarySearch .set nomips16 .set nomicromips .ent binarySearch .type binarySearch, @function binarySearch: .frame $fp,40,$31 # vars= 8, regs= 2/0, args= 16, gp= 8 .mask 0xc0000000,-4 .fmask 0x00000000,0 .set noreorder .cpload $25 .set nomacro addiu $sp,$sp,-40 sw $31,36($sp) sw $fp,32($sp) move $fp,$sp .cprestore 16 movz $31,$31,$0 sw $4,40($fp) sw $5,44($fp) sw $6,48($fp) sw $7,52($fp) lw $3,48($fp) lw $2,44($fp) nop slt $2,$3,$2 bne $2,$0,$L2 nop lw $3,48($fp) lw $2,44($fp) nop subu $2,$3,$2 srl $3,$2,31 addu $2,$3,$2 sra $2,$2,1 move $3,$2 lw $2,44($fp) nop addu $2,$3,$2 sw $2,24($fp) lw $2,24($fp) nop sll $2,$2,2 lw $3,40($fp) nop addu $2,$3,$2 lw $3,0($2) lw $2,52($fp) nop bne $3,$2,$L3 nop lw $2,24($fp) b $L4 nop $L3: lw $2,24($fp) nop sll $2,$2,2 lw $3,40($fp) nop addu $2,$3,$2 lw $3,0($2) lw $2,52($fp) nop slt $2,$2,$3 beq $2,$0,$L5 nop lw $2,24($fp) nop addiu $2,$2,-1 lw $7,52($fp) move $6,$2 lw $5,44($fp) lw $4,40($fp) lw $2,%got(binarySearch)($28) nop move $25,$2 .reloc 1f,R_MIPS_JALR,binarySearch 1: jalr $25 nop lw $28,16($fp) b $L4 nop $L5: lw $2,24($fp) nop addiu $2,$2,1 lw $7,52($fp) lw $6,48($fp) move $5,$2 lw $4,40($fp) lw $2,%got(binarySearch)($28) nop move $25,$2 .reloc 1f,R_MIPS_JALR,binarySearch 1: jalr $25 nop lw $28,16($fp) b $L4 nop $L2: li $2,-1 # 0xffffffffffffffff $L4: move $sp,$fp lw $31,36($sp) lw $fp,32($sp) addiu $sp,$sp,40 j $31 nop .set macro .set reorder .end binarySearch .size binarySearch, .-binarySearch .rdata .align 2 $LC0: .ascii "
Enter %d Element: " .align 2 $LC1: .ascii "%d " .text .align 2 .globl read_array .set nomips16 .set nomicromips .ent read_array .type read_array, @function read_array: .frame $fp,40,$31 # vars= 8, regs= 2/0, args= 16, gp= 8 .mask 0xc0000000,-4 .fmask 0x00000000,0 .set noreorder .cpload $25 .set nomacro addiu $sp,$sp,-40 sw $31,36($sp) sw $fp,32($sp) move $fp,$sp .cprestore 16 movz $31,$31,$0 sw $4,40($fp) sw $5,44($fp) sw $0,24($fp) sw $0,24($fp) b $L7 nop $L8: lw $2,24($fp) nop addiu $2,$2,1 move $5,$2 lw $2,%got($LC0)($28) nop addiu $4,$2,%lo($LC0) lw $2,%call16(printf)($28) nop move $25,$2 .reloc 1f,R_MIPS_JALR,printf 1: jalr $25 nop lw $28,16($fp) lw $2,24($fp) nop sll $2,$2,2 lw $3,44($fp) nop addu $2,$3,$2 move $5,$2 lw $2,%got($LC1)($28) nop addiu $4,$2,%lo($LC1) lw $2,%call16(__isoc99_scanf)($28) nop move $25,$2 .reloc 1f,R_MIPS_JALR,__isoc99_scanf 1: jalr $25 nop lw $28,16($fp) lw $2,24($fp) nop addiu $2,$2,1 sw $2,24($fp) $L7: lw $3,24($fp) lw $2,40($fp) nop slt $2,$3,$2 bne $2,$0,$L8 nop nop move $sp,$fp lw $31,36($sp) lw $fp,32($sp) addiu $sp,$sp,40 j $31 nop .set macro .set reorder .end read_array .size read_array, .-read_array .rdata .align 2 $LC2: .ascii "
%d " .text .align 2 .globl print_array .set nomips16 .set nomicromips .ent print_array .type print_array, @function print_array: .frame $fp,40,$31 # vars= 8, regs= 2/0, args= 16, gp= 8 .mask 0xc0000000,-4 .fmask 0x00000000,0 .set noreorder .cpload $25 .set nomacro addiu $sp,$sp,-40 sw $31,36($sp) sw $fp,32($sp) move $fp,$sp .cprestore 16 movz $31,$31,$0 sw $4,40($fp) sw $5,44($fp) sw $0,24($fp) sw $0,24($fp) b $L10 nop $L11: lw $2,24($fp) nop sll $2,$2,2 lw $3,44($fp) nop addu $2,$3,$2 lw $2,0($2) nop move $5,$2 lw $2,%got($LC2)($28) nop addiu $4,$2,%lo($LC2) lw $2,%call16(printf)($28) nop move $25,$2 .reloc 1f,R_MIPS_JALR,printf 1: jalr $25 nop lw $28,16($fp) lw $2,24($fp) nop addiu $2,$2,1 sw $2,24($fp) $L10: lw $3,24($fp) lw $2,40($fp) nop slt $2,$3,$2 bne $2,$0,$L11 nop nop move $sp,$fp lw $31,36($sp) lw $fp,32($sp) addiu $sp,$sp,40 j $31 nop .set macro .set reorder .end print_array .size print_array, .-print_array .rdata .align 2 $LC3: .ascii "
Enter Size of the Array " .align 2 $LC4: .ascii "
Enter key to serach " .align 2 $LC5: .ascii "
key not found " .align 2 $LC6: .ascii "
Key found at %d " .text .align 2 .globl main .set nomips16 .set nomicromips .ent main .type main, @function main: .frame $fp,48,$31 # vars= 16, regs= 2/0, args= 16, gp= 8 .mask 0xc0000000,-4 .fmask 0x00000000,0 .set noreorder .cpload $25 .set nomacro addiu $sp,$sp,-48 sw $31,44($sp) sw $fp,40($sp) move $fp,$sp .cprestore 16 movz $31,$31,$0 sw $0,28($fp) lw $2,%got($LC3)($28) nop addiu $4,$2,%lo($LC3) lw $2,%call16(printf)($28) nop move $25,$2 .reloc 1f,R_MIPS_JALR,printf 1: jalr $25 nop lw $28,16($fp) addiu $2,$fp,36 move $5,$2 lw $2,%got($LC1)($28) nop addiu $4,$2,%lo($LC1) lw $2,%call16(__isoc99_scanf)($28) nop move $25,$2 .reloc 1f,R_MIPS_JALR,__isoc99_scanf 1: jalr $25 nop lw $28,16($fp) lw $2,36($fp) addiu $3,$fp,28 move $5,$3 move $4,$2 lw $2,%got(read_array)($28) nop move $25,$2 .reloc 1f,R_MIPS_JALR,read_array 1: jalr $25 nop lw $28,16($fp) lw $2,36($fp) addiu $3,$fp,28 move $5,$3 move $4,$2 lw $2,%got(print_array)($28) nop move $25,$2 .reloc 1f,R_MIPS_JALR,print_array 1: jalr $25 nop lw $28,16($fp) nop lw $2,%got($LC4)($28) nop addiu $4,$2,%lo($LC4) lw $2,%call16(printf)($28) nop move $25,$2 .reloc 1f,R_MIPS_JALR,printf 1: jalr $25 nop lw $28,16($fp) addiu $2,$fp,32 move $5,$2 lw $2,%got($LC1)($28) nop addiu $4,$2,%lo($LC1) lw $2,%call16(__isoc99_scanf)($28) nop move $25,$2 .reloc 1f,R_MIPS_JALR,__isoc99_scanf 1: jalr $25 nop lw $28,16($fp) lw $2,36($fp) nop addiu $3,$2,-1 lw $4,32($fp) addiu $2,$fp,28 move $7,$4 move $6,$3 move $5,$0 move $4,$2 lw $2,%got(binarySearch)($28) nop move $25,$2 .reloc 1f,R_MIPS_JALR,binarySearch 1: jalr $25 nop lw $28,16($fp) sw $2,24($fp) lw $3,24($fp) li $2,-1 # 0xffffffffffffffff bne $3,$2,$L13 nop lw $2,%got($LC5)($28) nop addiu $4,$2,%lo($LC5) lw $2,%call16(printf)($28) nop move $25,$2 .reloc 1f,R_MIPS_JALR,printf 1: jalr $25 nop lw $28,16($fp) b $L14 nop $L13: lw $2,24($fp) nop addiu $2,$2,1 move $5,$2 lw $2,%got($LC6)($28) nop addiu $4,$2,%lo($LC6) lw $2,%call16(printf)($28) nop move $25,$2 .reloc 1f,R_MIPS_JALR,printf 1: jalr $25 nop lw $28,16($fp) $L14: move $2,$0 move $sp,$fp lw $31,44($sp) lw $fp,40($sp) addiu $sp,$sp,48 j $31 nop .set macro .set reorder .end main
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.