The binary search algorithm uses left and right to mark the end points of the se
ID: 3769925 • Letter: T
Question
The binary search algorithm uses left and right to mark the end points of the section of the array in which the number might reside. left starts out at element 0 and right starts out as the index of the last element of the array. The algorithm then computes the index of the middle element of the array: middle = (left + right) / 2. There are two base cases: •If element middle in the array is the number for which we are searching, then the algorithm is done, and returns middle. •Normally, left will be less than right. When left becomes greater than right, the element is not in the array. In this case, search will return -1 to indicate the element is not present. There are two recursive cases, depending on which half of the array might contain the value for which we are searching: •If the search value is less than the value at index middle, then set right to middle - 1 and call search recursively. •If the search value is greater than the value at middle, then set left to middle + 1 and call search recursively. search Function: The search function will take 5 parameters: •$a0 = address of element zero of the array of values •$a1 = value to search for •$a2 = left index •$a3 = right index •5th parameter = level where level is how deep the recursion has gone; i.e., how many times search has been called while looking for the current value. When main calls search, main will pass 1 as the value for level. Each time search is called recursively, your function will pass level + 1. main and newLines Functions: main will create an array of values used for searching. main will call search with level = 1, left index = 0, and right index = index of the last element in the array. The newLines procedure will be called anytime that a newline needs to be printed. You can see examples of such calls in the main procedure in the provided test cases. Your search function will call newLines anytime that search needs to print one or more newline characters. The newLines procedure takes one argument, passed in $a0. The argument will indicate the number of newlines to be printed. Examples: Here is the provided test07.s file: # This is the test case shown in the program description. # Searches for 28, which is present in the array. .data mainNumValues: .word 17 mainValues: .word 3 #mainValues[0] .word 4 #mainValues[1] .word 7 #mainValues[2] .word 8 #mainValues[3] .word 10 #mainValues[4] .word 13 #mainValues[5] .word 23 #mainValues[6] .word 28 #mainValues[7] .word 33 #mainValues[8] .word 43 #mainValues[9] .word 44 #mainValues[10] .word 47 #mainValues[11] .word 53 #mainValues[12] .word 54 #mainValues[13] .word 63 #mainValues[14] .word 66 #mainValues[15] .word 73 #mainValues[16] mainSearchValue: .word 28 mainResultString: .asciiz "main: search returned " mainDashes: .asciiz "----------------------------------------" mainSearchStr: .asciiz "main searching for " .text main: # Function prologue -- even main has one addiu $sp, $sp, -24 # allocate stack space -- default of 24 sw $ra, 4($sp) # save return address sw $fp, 0($sp) # save frame pointer of caller addiu $fp, $sp, 20 # setup frame pointer for main # Print dashes la $a0, mainDashes addi $v0, $zero, 4 syscall # print 1 newline addi $a0, $zero, 1 jal newLines la $a0, mainSearchStr addi $v0, $zero, 4 syscall la $t0, mainSearchValue lw $a0, 0($t0) addi $v0, $zero, 1 syscall # print 2 newlines addi $a0, $zero, 2 jal newLines # Call search( mainValues, searchNum, left=0, right=mainNumValues-1, level=0 ) addi $t0, $zero, 1 sw $t0, -4($sp) # level = 1 la $t0, mainNumValues lw $a3, 0($t0) addi $a3, $a3, -1 # $a3 = right = mainNumValues - 1 addi $a2, $zero, 0 # $a2 = left = 0 la $t0, mainSearchValue lw $a1, 0($t0) # $a1 = value we are searching for la $a0, mainValues # $a0 = &mainValues[0] jal search addi $t0, $v0, 0 # copy result to $t0 la $a0, mainResultString addi $v0, $zero, 4 syscall addi $a0, $t0, 0 # print the result addi $v0, $zero, 1 syscall # Print 1 newline addi $a0, $zero, 1 jal newLines # Print dashes la $a0, mainDashes addi $v0, $zero, 4 syscall # print 1 newline addi $a0, $zero, 1 jal newLines mainDone: # Epilogue for main -- restore stack & frame pointers lw $ra, 4($sp) # get return address from stack lw $fp, 0($sp) # restore frame pointer of caller addiu $sp, $sp, 24 # restore stack pointer of caller jr $ra # return to caller .data newLinesStr: .asciiz " " .text newLines: # Function prologue addiu $sp, $sp, -24 # allocate stack space -- default of 24 sw $a0, 8($sp) # save $a0 = number of newlines to print sw $ra, 4($sp) # save return address sw $fp, 0($sp) # save frame pointer of caller addiu $fp, $sp, 20 # setup frame pointer for newLines # for (i = 0; i < numNewLines; i++) # print newLinesStr addi $t0, $zero, 0 # $t0 = i = 0 addi $t1, $a0, 0 # $t1 = number of newlines to print la $a0, newLinesStr newLinesLoopBegin: slt $t2, $t0, $t1 # $t2 = i < numNewLines beq $t2, $zero, newLinesLoopEnd addi $v0, $zero, 4 syscall addi $t0, $t0, 1 # i++ j newLinesLoopBegin newLinesLoopEnd: # Epilogue for newLines -- restore stack & frame pointers and return lw $ra, 4($sp) # get return address from stack lw $fp, 0($sp) # restore frame pointer of caller addiu $sp, $sp, 24 # restore stack pointer of caller jr $ra # return to caller # Your code goes below this line Example outputs: The output for the example above, where 28 is the search value: ---------------------------------------- main searching for 28 search level 1, left 0, right 16 search level 1 making recursive call search level 2, left 0, right 7 search level 2 making recursive call search level 3, left 4, right 7 search level 3 making recursive call search level 4, left 6, right 7 search level 4 making recursive call search level 5, left 7, right 7 search level 5 found number in location 7 search level 5 done, returning 7 search level 4 done, returning 7 search level 3 done, returning 7 search level 2 done, returning 7 search level 1 done, returning 7 main: search returned 7 ---------------------------------------- To test other possibilities, you can simply change mainSearchValue to be a different number that is, or is not, in the array. For example, if mainSearchValue is 63, the output should be: ---------------------------------------- main searching for 63 search level 1, left 0, right 16 search level 1 making recursive call search level 2, left 9, right 16 search level 2 making recursive call search level 3, left 13, right 16 search level 3 found number in location 14 search level 3 done, returning 14 search level 2 done, returning 14 search level 1 done, returning 14 main: search returned 14 ---------------------------------------- If mainSearchValue is 57, a value that is not in the array, the output should be: ---------------------------------------- main searching for 57 search level 1, left 0, right 16 search level 1 making recursive call search level 2, left 9, right 16 search level 2 making recursive call search level 3, left 13, right 16 search level 3 making recursive call search level 4, left 13, right 13 search level 4 making recursive call search level 5, left 14, right 13 search level 5 did not find number in array search level 5 done, returning -1 search level 4 done, returning -1 search level 3 done, returning -1 search level 2 done, returning -1 search level 1 done, returning -1 main: search returned -1 ----------------------------------------
Explanation / Answer
public class MyRecursiveBinarySearch {
public static int recursiveBinarySearch(int[] sortedArray, int start, int end, int key,int level) {
if (start < end) {
int mid = start + (end - start) / 2;
if (key < sortedArray[mid]) {
return recursiveBinarySearch(sortedArray, start, mid, key,level+1);
} else if (key > sortedArray[mid]) {
return recursiveBinarySearch(sortedArray, mid+1, end , key,level+1);
} else {
printNewLine(level);
return mid;
}
}
return -(start + 1);
}
public static void main(String[] args) {
int[] arr1 = {2,45,234,567,876,900,976,999};
int index = recursiveBinarySearch(arr1,0,arr1.length,45,1);
System.out.println("Found 45 at "+index+" index");
}
public void printNewLine(int a) {
for(int i=0;i<a;i++) {
System.out.println();
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.