GATE DS&AI 2024 | Question: 30

Question

​​​​​Let $F(n)$ denote the maximum number of comparisons made while searching for an entry in a sorted array of size $n$ using binary search.

Which ONE of the following options is TRUE?

• A. $F(n)=F(\lfloor n / 2\rfloor)+1$
• B. $F(n)=F(\lfloor n / 2\rfloor)+F(\lceil n / 2\rceil)$
• C. $F(n)=F(\lfloor n / 2\rfloor)$
• D. $F(n)=F(n-1)+1$

Answer 1

In binary search, at each step, you compare the target element with the middle element of the array. Based on the comparison result, you recursively search either the left or the right half of the array.

Let's denote \( F(n) \) as the maximum number of comparisons made while searching for an entry in a sorted array of size \( n \) using binary search.

For an array of size \( n \):

- At each step, you make 1 comparison to check if the target is equal to the middle element.

- Then, you either search the left half or the right half of the array.

- So, the maximum number of comparisons for an array of size \( n \) is \( F(n) = 1 + F\left(\left\lfloor\frac{n}{2}\right\rfloor\right) \).

So, the correct option is:
A. \( F(n) = F\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + 1 \)