÷ is division; when the result is assigned to an integer variable (including a function argument), the fractional part is discarded. The following program finds in lo the index of the first value that is at least x in the integer array data, which is sorted in ascending order (indices start at 1). x is no greater than the last element of data. What should replace 【a】 in the program?

Answer: C. mid + 1

If data[mid] < x, then data[mid] and every element before it are less than x, so the answer is at mid + 1 or later. Otherwise data[mid] ≧ x and the answer is at mid or earlier, so hi ← mid. With lo ← mid + 1 the range always shrinks, and the answer is where lo = hi. With lo ← mid, when lo and hi are adjacent mid = lo, and if data[mid] < x the range does not shrink and the loop never ends.

• A. When lo and hi are adjacent and data[lo] < x, mid stays equal to lo, the range does not shrink and the loop never ends. For example, with data = {3, 8, 12, 17, 23, 31} and x = 31, lo = 5 and hi = 6 forever.
• B. This can move lo back before the answer, so the range may not shrink. With data = {3, 8, 12, 17, 23, 31} and x = 4, lo becomes 0 and the loop never ends.
• C. Correct. It removes mid, now known to be less than x, so the range always shrinks.