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
Write a Java program that randomly generates an array of 500,000 integers between 0 and 499,999,...
Write a Java program that randomly generates an array of 500,000 integers between 0 and 499,999, and then prompts the user for a search key value. Estimate the execution time of invoking the linearSearch method in Listing A below. Sort the array and estimate the execution time of invoking the binarySearch method in Listing B below. You can use the following code template to obtain the execution time: long startTime = System.currentTimeMillis(); perform the task; long endTime = System.currentTimeMillis(); long...
What is wrong with my recursive Binary Search code? For some reason my 'middle' value is...
What is wrong with my recursive Binary Search code? For some reason my 'middle' value is always zero? Please fix and explain! #include <stdio.h> #include <stdlib.h> #include <stdbool.h> int BinarySearch(const int A[],const int L,const int R,const int key) {              if (R >= 1){           int middle = L + (R-1)/2;                              if (A[middle] == key)        return A[middle];               if (A[middle] > key){...
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)...
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 ==...
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...
8.15 *zyLab: Method Library (Required & Human Graded) This code works but there are some problems...
8.15 *zyLab: Method Library (Required & Human Graded) This code works but there are some problems that need to be corrected. Your task is to complete it to course style and documentation standards CS 200 Style Guide. This project will be human graded. This class contains a set of methods. The main method contains some examples of using the methods. Figure out what each method does and style and document it appropriately. The display method is done for you and...
my code has several functions; delete and backward functions are not working, rewrite the code for...
my code has several functions; delete and backward functions are not working, rewrite the code for both functions and check them in the main: #include<iostream> #include<cassert> using namespace std; struct nodeType {    int info;    nodeType *link; }; class linkedList { public:    void initializeList();    bool isEmptyList();    void print();    int length();    void destroyList();    void insertFirst(int newItem);    void insertLast(int newItem);    int front();    linkedList();    void copyList(const linkedList otherList);    void insertNewValue(int value);...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT