GATE CS 2008 Q84 — Searching, Sorting, Hashing

The given binary search implementation has a bug: when updating the search boundaries, it uses i = k instead of i = k + 1, and j = k instead of j = k - 1. This can lead to an infinite loop when the search range cannot be reduced further.

Let us trace Option C where $Y = [2, 2, 2, 2, 2, 2, 2, 2, 2, 2]$ and $x > 2$ (let $x = 3$):

• Initial state: $i = 0$, $j = 9$
• Iteration 1: $k = \lfloor(0+9)/2\rfloor = 4$. Since $Y[4] = 2 < 3$, we set $i = k = 4$. Condition $(Y[4] \neq 3) \land (4 < 9)$ is true.
• Iteration 2: $k = \lfloor(4+9)/2\rfloor = 6$. Since $Y[6] = 2 < 3$, we set $i = k = 6$. Condition $(Y[6] \neq 3) \land (6 < 9)$ is true.
• Iteration 3: $k = \lfloor(6+9)/2\rfloor = 7$. Since $Y[7] = 2 < 3$, we set $i = k = 7$. Condition $(Y[7] \neq 3) \land (7 < 9)$ is true.
• Iteration 4: $k = \lfloor(7+9)/2\rfloor = 8$. Since $Y[8] = 2 < 3$, we set $i = k = 8$. Condition $(Y[8] \neq 3) \land (8 < 9)$ is true.
• Iteration 5: $k = \lfloor(8+9)/2\rfloor = 8$. Since $Y[8] = 2 < 3$, we set $i = k = 8$. Condition $(Y[8] \neq 3) \land (8 < 9)$ is true.

At this point, $i = 8$ and $j = 9$ remain unchanged, and $k$ remains $8$ in all subsequent iterations. The program enters an infinite loop and fails to terminate.