GATE CS 2008 Q85 — Searching, Sorting, Hashing

To identify the error in the given binary search implementation, let us analyze the behavior of the loop updates when the search interval becomes small.

Consider an array $Y = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]$ and we are searching for $x = 5$.

• Initially, $i = 0$ and $j = 9$.
• $k = (0 + 9) / 2 = 4$. Since $Y[4] = 16 > 5$, the else branch executes: $j = k = 4$.
• Next iteration: $k = (0 + 4) / 2 = 2$. Since $Y[2] = 8 > 5$, we get $j = k = 2$.
• Next iteration: $k = (0 + 2) / 2 = 1$. Since $Y[1] = 5 == x$, the loop terminates (due to the condition Y[k] != x), and the element is correctly found.

Now, consider searching for $x = 6$ (which is not in the array):

• Eventually, we reach a state where $i = 1$ and $j = 2$.
• $k = (1 + 2) / 2 = 1$.
• Since $Y[1] = 5 < 6$, the if branch executes: $i = k = 1$.
• In the next iteration, $i$ and $j$ remain $1$ and $2$ respectively. $k$ is calculated as $1$ again. This results in an infinite loop because the search space never shrinks.

Correction:

To guarantee that the search space strictly shrinks in every step and to avoid infinite loops, we must exclude the index $k$ once we determine that $Y[k] \neq x$:

• If $Y[k] < x$, then $x$ must lie in the strictly right subarray, so we set $i = k + 1$.
• If $Y[k] > x$, then $x$ must lie in the strictly left subarray, so we set $j = k - 1$.

Thus, changing line 6 to if (Y[k] < x) i = k + 1; else j = k - 1; makes the program work correctly.