Question

Do a trace on the binarySearch method below: variable key holds the value 17, and variable...

Do a trace on the binarySearch method below: variable key holds the value 17, and

variable list is a reference to an array with these values {9, 20, 23, 28, 33, 38, 42, 48, 54, 61,73}.

public static int binarySearch(int[] list, int key) {

    int lowIndex = 0;

    int highIndex = list.length - 1;

    while (highIndex >= lowIndex) {

      int midIndex = (lowIndex + highIndex) / 2;

      if (key < list[midIndex]){

           highIndex = midIndex - 1;

     }

      else if (key > list[midIndex]){

           lowIndex = midIndex + 1;      

     }

      else if (key == list[midIndex]){

           return midIndex;            

     }

    } // end of while loop

    return -1;

} // end of binary search method

Each row in the table below corresponds to one iteration of the while loop in the method above. You can add or remove rows according to the actual number of iterations. The first row’s information corresponds to the first iteration, and its value has been filled. You need to continue for the following rows.

key

lowIndex

highIndex

highIndex>=lowIndex

midIndex

key==list[midIndex]

key<list[midIndex]

17

0

10

true

5

false

true

Given the key value and array content listed above, what is the return value of the binary search method?

Homework Answers

Answer #1

The table is:

key   lowIndex   highIndex   highIndex>=lowIndex   midIndex   key==list[midIndex]   key<list[midIndex]
17 0 10 true 5 false true
17 0 4 true 2 false true
17 0 1 true 0 false false
17 1 1 true 1 false true

The return value of the binary search method is -1 because highIndex == lowIndex value is true and key == list[midIndex] value if false, so it exists the while loop and after it exists the while loop only one value is returned i.e. -1.

If you have any queries regarding the table/answer comment down below. I will help you out as soon as possible.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
do a code trace on how a key gets deleted package interview; import java.util.*; public class...
do a code trace on how a key gets deleted package interview; import java.util.*; public class binarySearchTree { Node root; void insert(int key) { root = insertRec(root,key); } void delete(int key) { root = deleteRec(root,key); } Node insertRec(Node root, int key) { if(root == null) { root = new Node(key); return root; } if(key < root.key) { root.leftChild = insertRec(root.leftChild,key); } else if(key > root.key){ root.rightChild = insertRec(root.rightChild,key); } return root; } Node deleteRec(Node root, int key) { if(root ==...
Build two arrays[ ] (Integer and String) and convert them to two ArrayLists and write two...
Build two arrays[ ] (Integer and String) and convert them to two ArrayLists and write two overloaded generic static search method to find the index locations of a specified value. One of the search methods applies to the array type while the other (overloaded) search method applies to the collection type. Implement the following generic linear search method and write a client program to display results: (Here is the header) public static <E extends Comparable<E>> int search(E[] list, E key)...
Restricted structures such as stack and queue are fast, but they do not support access in...
Restricted structures such as stack and queue are fast, but they do not support access in the key field mode. Group of answer choices True False Big O analysis evaluates an algorithm based on its _________ performance. Group of answer choices A. average-case B. best-case C. worst-case Which of the following algorithms is the fastest in speed? Group of answer choices A. Polynomial time algorithm B. Linear time algorithm C. Exponential time algorithm The following code gives an implementation of...
convert this code to accept int value instead of float values using python. Make sure to...
convert this code to accept int value instead of float values using python. Make sure to follow the same code. do not change the steps and make sure to point to what code you replaced. make sure to have 2 files Method:----------------------- #define a python user difined method def get_float_val (prompt): is_num = False str_val = input (prompt) #prming read for our while #while is_num == False: (ignore this but it works) old school while not is_num: try: value =...
Take a look at the file GenericMethods.java. There are three methods you must implement: ·public static...
Take a look at the file GenericMethods.java. There are three methods you must implement: ·public static <T extends Comparable<T>> int findMin(T[] arr): Iterate through the array to find the index of the smallest element in the array. If there are two elements with the smallest value, the method should return the index of the first one. The method should run in O(n). ·public static <T extends Comparable<T>> int findMinRecursive(T[] arr): Should behave just like findMin, but should be implemented recursively....
This code listens to keypresses and displays the ASCII code of the key pressed on the...
This code listens to keypresses and displays the ASCII code of the key pressed on the LEDs. Port A needs to be connected to the keypad and port D needs to be connected to the LED port. I need you Modify the code such that the array is cleared when the ‘*’ key is pressed and an LED is turned on when the ‘#’ key is pressed. #include <avr/io.h> #define F_CPU 8000000UL #include <util/delay.h> // Delay header #define KEY_PRT PORTA...
IN JAVA Iterative Linear Search, Recursive Binary Search, and Recursive Selection Sort: <-- (I need the...
IN JAVA Iterative Linear Search, Recursive Binary Search, and Recursive Selection Sort: <-- (I need the code to be written with these) I need Class river, Class CTRiver and Class Driver with comments so I can learn and better understand the code I also need a UML Diagram HELP Please! Class River describes river’s name and its length in miles. It provides accessor methods (getters) for both variables, toString() method that returns String representation of the river, and method isLong()...
The following program creates a linked list which contains 5 links. Add a method called doubleValue()...
The following program creates a linked list which contains 5 links. Add a method called doubleValue() to the LinkedList class. The doubleValue() method must double the value of the number data field in each link. Add the required code to the main() method to call the doubleValue() method and display the revised list. public class Link { private int number; private Link next;      public Link(int x) { number = x; }    public void displayLink() { System.out.println("The number is:...
The following program creates a linked list which contains 5 links. Add a method called doubleValue()...
The following program creates a linked list which contains 5 links. Add a method called doubleValue() to the LinkedList class. The doubleValue() method must double the value of the number data field in each link. Add the required code to the main() method to call the doubleValue() method and display the revised list. public class Link { private int number; private Link next;      public Link(int x) { number = x; }    public void displayLink() { System.out.println("The number is:...
Answer question for C# 1 of 10 When items are added or removed, a list resizes...
Answer question for C# 1 of 10 When items are added or removed, a list resizes itself. True False Question 2 of 10 What happens when you assign one list to another using the assignment operator? An error message generates. Elements copy to new memory locations. Both lists become value-type data elements. Both lists reference the same memory locations. Question 3 of 10 Which of the following is a valid example of calling a method and sending it an array...