The GATE Grind

GATE 2024 DA – Question 40

Programming, Data Structures and Algorithms · Searching and sorting algorithms · 2 marks · Multiple choice

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?

  1. $F(n) = F(\lfloor n/2 \rfloor) + 1$
  2. $F(n) = F(\lfloor n/2 \rfloor) + F(\lceil n/2 \rceil)$
  3. $F(n) = F(\lfloor n/2 \rfloor)$
  4. $F(n) = F(n - 1) + 1$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $F(n) = F(\lfloor n/2 \rfloor) + 1$

Explanation

Binary search compares with the middle element, and then continues in one half only (the larger half has at most $\lfloor n/2 \rfloor$ elements). So in the worst case it makes one comparison and then searches an array of size $\lfloor n/2 \rfloor$, which gives $F(n) = F(\lfloor n/2 \rfloor) + 1$. This is the recurrence for $\lfloor \log_2 n \rfloor + 1$ comparisons.