Given an array arr = {45, 77, 89, 90, 94, 99, 100} and key = 100, what are the…
2024
Given an array arr = {45, 77, 89, 90, 94, 99, 100} and key = 100, what are the mid values (corresponding array elements) generated in the first and second iterations of a standard iterative binary search?
- A.
90 and 99
- B.
90 and 100
- C.
89 and 94
- D.
94 and 99
Attempted by 6 students.
Show answer & explanation
Correct answer: A
Iterative binary search keeps a search window defined by two indices, low and high, over a SORTED array. Each iteration computes mid = floor((low + high) / 2), compares the key to arr[mid], and narrows the window: if key is greater than arr[mid] the left half is discarded by setting low = mid + 1; if key is smaller, the right half is discarded by setting high = mid - 1; the loop stops once arr[mid] equals the key.
Applying this to arr = {45, 77, 89, 90, 94, 99, 100} (0-indexed, size 7) and key = 100:
Iteration 1 - low = 0, high = 6, so mid = floor((0 + 6) / 2) = 3, giving arr[3] = 90. Since key (100) is greater than 90, the left half is discarded: low is updated to mid + 1 = 4.
Iteration 2 - low = 4, high = 6, so mid = floor((4 + 6) / 2) = 5, giving arr[5] = 99. Since key (100) is greater than 99, low is updated again to mid + 1 = 6.
Iteration 3 (cross-check) - low = 6, high = 6, so mid = 6, giving arr[6] = 100, which equals the key - confirming the window was narrowed correctly across the first two iterations before the match was found.
So the mid elements produced in the first and second iterations are 90 and 99 respectively.