Question

For the binarySearch method in Section 7.10.2, what is low and high after the first iteration of the while loop when invoking binarySearch(new int[]{1, 4, 6, 8, 10, 15, 20}, 11)

Answer 1

Low is at index 4

High is at index 6

Step-by-step explanation:

As the array index starts from 0 to n, therefore the values in the array will have following indices.

`Index:\;\;\;\;\;0\;\;\;\;\;1\;\;\;\;\;2\;\;\;\;\;3\;\;\;\;\;\;4\;\;\;\;\;\;\;5\;\;\;\;\;\;6\\\\Value:\;\;\;\;\;1\;\;\;\;\;4\;\;\;\;\;6\;\;\;\;\;8\;\;\;\;\;10\;\;\;\;\;15\;\;\;\;\;20`

For the first iteration of the while loop, for the key "11" the binarySearch will declare index 0 (value of 1) as the low, index 3 (value of 8) and index 6 (value 20) as the high. However, since the key "11" is to the right of mid, therefore in the next iteration, binarySearch will search in the region after the index 3. Hence, after the first iteration, index 4 (value of 10) will be low, index 5 (value of 15) will be mid and index 6 (value of 20) will be high.