GATE 2024 DA Q.40: solution and answer

Official answer: ASource: Official answer key, GATE 2024 DA (IISc Bengaluru)

1. Binary search compares the key with the middle element once. If it is not a match, the search continues in exactly one of the two remaining parts, never both.

2. With the middle element removed from an array of size $n$, the two parts have sizes $\lfloor (n-1)/2\rfloor$ and $\lfloor n/2\rfloor$. The larger part therefore has exactly $\lfloor n/2\rfloor$ elements. The worst case is when the key lies in the larger part (or is absent).

3. So the worst case is one comparison plus the worst case on $\lfloor n/2\rfloor$ elements: $F(n)=F(\lfloor n/2\rfloor )+1$ with $F(1)=1$. This solves to $F(n)=\lfloor {\log }_{2}n\rfloor +1$. Values: $F(1)=1$, $F(2)=2$, $F(3)=2$, $F(4)=3$, $F(5)=3$.

4. Check (B): $F(n)=F(\lfloor n/2\rfloor )+F(\lceil n/2\rceil )$ would add the costs of both halves, as an algorithm does when it processes both halves. It gives $F(2)=F(1)+F(1)=2$, but $F(4)=F(2)+F(2)=4$, whereas the true value is $F(4)=3$. So (B) is false.

5. Check (C): $F(n)=F(\lfloor n/2\rfloor )$ ignores the comparison at the middle. At $n=2$ it says $F(2)=F(1)=1$, but binary search on two elements can need 2 comparisons. So (C) is false.

6. Check (D): $F(n)=F(n-1)+1$ would give $F(3)=F(2)+1=3$, but the true value is $F(3)=2$. It describes linear search, not binary search. So (D) is false.

7. Only (A) is true.