GATE CSE 2021 Set 2 Q18: Arithmetic operations in recursive binary search

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$ ?

Try it: multiple choice: exactly one correct option

Wrong answer costs 1/3 mark in GATE.

Show answer and explanation

Answer: B (official GATE 2021 final answer key)

Concept used: Each call does a constant number of arithmetic operations (computing the middle index) and halves the range.

First step: Write the recurrence $T(n) = T(n/2) + c$ for the worst case (key not found).

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2021 Set 2 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key