Lesson 7.7 · Trace it
Trace: binary search missing (Java)
Java code8 rows to fill3 marks
Complete the trace table for this Java code. The array is sorted, so this is a binary search for a value that is not in it. Dividing two int values in Java throws away the remainder. Then answer the question below the table. [3]
Line 1: int[] values = {6, 11, 15, 22, 28, 35, 41};Line 2: int target = 30;Line 3: int low = 0;Line 4: int high = values.length - 1;Line 5: boolean found = false;Line 6: while (low <= high && !found) {Line 7, indented 1 level: int mid = (low + high) / 2;Line 8, indented 1 level: if (values[mid] == target) {Line 9, indented 2 levels: found = true;Line 10, indented 1 level: } else if (values[mid] < target) {Line 11, indented 2 levels: low = mid + 1;Line 12, indented 1 level: } else {Line 13, indented 2 levels: high = mid - 1;Line 14, indented 1 level: }Line 15: }
Fill in one row each time a line changes low, high or mid. The table already has the right number of rows. In each row, write only what that line changes; you can leave the other cells empty or copy their values down. Write values the way Java shows them: 3 and 3.0 are different, and text goes in quotes.
| Row | low | high | mid |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
| 6 | |||
| 7 | |||
| 8 |