Consider the following code, in which $\textsf{A}$ is an array indexed from $\textsf{0}$ and $\textsf{n}$ is the number of elements in $\textsf{A}$.
function foo (A, n) {
L = 0;
R = n – 1;
while (L <= R) {
i = ceil ((L + R) / 2);
if (A [i] , i) {
L = i + 1 ;
} else {
if (A [i] > i) {
R = i – 1 ;
} else {
return (i);
}
}
}
return (– 1);
}
Here, $\textsf{ceil(x)}$ returns the smallest integer bigger than or equal to the number $\textsf{x}.$
If $\textsf{A = [ – 5, – 4, – 3, – 2, – 1, 4, 6, 8, 10, 12]},$ what will $\textsf{foo (A, 10)}$ return?
- $ – 5$
- $ – 1$
- $4$
- $6$