chapter

Searching Algorithms and Binary Search PYQs for GATE DA

Solve 3+ Searching Algorithms and Binary Search previous year questions for GATE DA with answers and detailed solutions. Free sample questions below.

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

2026 PYQ

Level 3: Exam Standard

Let A be a sorted array containing 1000 distinct integers. You perform a recursive binary search on A to find an element y. Suppose each comparison checks whether the middle element computed during the current recursive step is equal to, less than, or greater than y. The maximum number of comparisons that may have to be performed if y is not an element of A is _______ . (Answer in integer)

Question 2

2025 PYQ

Level 3: Exam Standard

For which of the following inputs does binary search take time O (lo g n) in the worst case?

Question 3

2024 PYQ

Level 3: Exam Standard

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?

Free preview ends here

Login to view the complete previous-year questions and solutions

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Searching Algorithms and Binary Search PYQs for GATE DA

Solve 3+ Searching Algorithms and Binary Search previous year questions for GATE DA with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Searching Algorithms and Binary Search

Chapter Journey

Searching Algorithms and Binary Search

Step 1: The Mathematical Engine

Binary Search Recurrence and Worst-Case Comparisons

Master the exact math, recurrence relations, and depth calculations.

Step 2: The Physical Constraints

Binary Search Preconditions and Data Representation

Understand the strict structural rules for the algorithm to function.

Goal: Mathematically prove efficiency and identify exact structural limitations.

The Core Intuition: Divide and Conquer

The Core Intuition

Binary search is the ultimate divide and conquer strategy for sorted data.

The Mental Model

Imagine searching a physical dictionary. You open it exactly to the middle. If the target comes before the middle page, you ignore the entire right half. You cut a massive problem exactly in half.

The Mathematical Magic

The speed comes from the problem size shrinking by a constant fraction at every step.

Linear n, n-1, n-2 ...

Binary n, n/2, n/4 ...

Searching Algorithms and Binary Search: Solved Questions with Step-by-Step Explanations (3 Problems)

Question 1 · Programming, Data Structures and Algorithms · 2026 NAT

Let A be a sorted array containing 1000 distinct integers. You perform a recursive binary search on A to find an element y. Suppose each comparison checks whether the middle element computed during the current recursive step is equal to, less than, or greater than y.
The maximum number of comparisons that may have to be performed if y is not an element of A is _______ . (Answer in integer)

Correct Answer:

10.00

Step-by-Step Solution

Insight: A 3-way comparison counts as exactly 1 comparison per step. The max comparisons is simply the depth of the recursion tree.

Exam route: Use the formula $⌊ lo g_{2} n ⌋ + 1$ . For $n = 1000$ , $⌊ 9.96 ⌋ + 1 = 10$ .

Learning route:

The problem specifies a 3-way comparison (equal, less, greater). This counts as 1 comparison per recursive step.

The maximum number of comparisons is the maximum depth of the recursion tree, which occurs when the element is not found or is at the deepest leaf.

The exact formula for the maximum depth (number of comparisons) is $⌊ lo g_{2} n ⌋ + 1$ .

Given $n = 1000$ :

$lo g_{2} 1000 \approx 9.965$ .

$⌊ 9.965 ⌋ = 9$ .

Total comparisons = $9 + 1 = 10$ .

If the problem had specified two separate checks (e.g., if A[mid] == y then else if A[mid] < y), the worst case would be 2 comparisons per step, yielding 20. But the 3-way comparison explicitly avoids this trap.

Question 2 · Programming, Data Structures and Algorithms · 2025 MCQ

For which of the following inputs does binary search take time $O (lo g n)$ in the worst case?

A.
An array of $n$ integers in any order
B.
A linked list of $n$ integers in any order
C.
An array of $n$ integers in increasing order
D.
A linked list of $n$ integers in increasing order

Correct Answer:

Step-by-Step Solution

Insight: Binary search requires both sorted data (for elimination) and random access (for $O (1)$ mid calculation).

Exam route: Check options for "sorted" and "array". Only "array in increasing order" satisfies both.

Learning route:

Binary search achieves $O (lo g n)$ time complexity by halving the search space at each step.

This requires two strict preconditions:

The data must be sorted, so we can mathematically guarantee which half contains the target.
The data structure must support $O (1)$ random access, so we can find the middle element in constant time.

Arrays provide contiguous memory allocation, allowing $O (1)$ random access via index math.

Linked lists require $O (n)$ traversal to find the middle node, collapsing the time complexity to $O (n lo g n)$ or worse.

Therefore, only a sorted array (increasing order) guarantees $O (lo g n)$ worst-case time.

Question 3 · Programming, Data Structures and Algorithms · 2024 MCQ

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 (⌊ n /2 ⌋) + 1$
B.
$F (n) = F (⌊ n /2 ⌋) + F (⌈ n /2 ⌉)$
C.
$F (n) = F (⌊ n /2 ⌋)$
D.
$F (n) = F (n - 1) + 1$

Correct Answer:

Step-by-Step Solution

Insight: Binary search divides the problem into one half, not both. The recurrence must reflect a single recursive call plus the current step.

Exam route: Identify the worst-case subproblem size as $⌊ n /2 ⌋$ . Add 1 for the current comparison. Match with $F (n) = F (⌊ n /2 ⌋) + 1$ .

Learning route:

In binary search, we compare the target with the middle element. This takes 1 comparison.

Then, we discard half the array and recurse on the other half.

The worst-case scenario is when the remaining half is as large as possible.

For an array of size $n$ , the two halves have sizes $⌊(n - 1) /2 ⌋$ and $⌈(n - 1) /2 ⌉$ . The maximum of these is $⌊ n /2 ⌋$ .

Thus, the maximum number of comparisons $F (n)$ satisfies the recurrence:

$F (n) = F (⌊ n /2 ⌋) + 1$ .

Option A matches this. Option B implies searching both halves. Option C misses the current comparison. Option D is for linear search.

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Searching Algorithms and Binary Search PYQs for GATE DA

Chapter Roadmap: Searching Algorithms and Binary Search

Chapter Journey

Step 1: The Mathematical Engine

Step 2: The Physical Constraints

The Core Intuition: Divide and Conquer

The Core Intuition

The Mental Model

The Mathematical Magic

Searching Algorithms and Binary Search: Solved Questions with Step-by-Step Explanations (3 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit