What are common examiner traps in Searching?

Misreading 'NOT the largest' as 'find the largest' or 'find the second largest' and incorrectly choosing N-1 or N + ⌈ log2 N ⌉ - 2. Assuming that verifying a property on an unordered list always requires inspecting all N elements.

GATE CSE Searching PYQs

Standard yield0.5% of Algorithms

In this topic, GATE evaluates the fundamental understanding of comparison-based bounds and logical deduction on unordered lists. Rather than standard search alg… Read the guide

Take topic test

Questions: 1
Asked: 2025
Total marks: 1
Marks / paper: 0

1 GATE CSE Searching PYQs with solutions, from Algorithms. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

GATE CSE 2025 Set 2 · Q20Consider an unordered list of $N$ distinct integers. What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?MCQ1 markEasySolve

What GATE tests in Searching

Concepts, patterns, formulas and traps distilled from past papers.

In this topic, GATE evaluates the fundamental understanding of comparison-based bounds and logical deduction on unordered lists. Rather than standard search algorithms (linear/binary search), questions test the exact minimum number of comparisons needed to satisfy non-standard or relaxed selection conditions.

Core concepts

Comparison model of computation
Lower bounds on comparisons for non-extremal search
Properties of partial orders established via pairwise comparison

Recurring question patterns

Minimum comparisons for relaxed selection criteria
RareMCQ1 marks2025
Determining the minimum number of element-to-element comparisons required to identify an element satisfying a relaxed property (e.g., finding an element that is strictly not the maximum or not the minimum).

Formulas GATE uses

Non-extremal Identification Bound

\text{Comparisons} = 1

Used when identifying any element guaranteed not to be the maximum (or minimum) from an unordered set of $N \ge 2$ distinct elements by comparing any two arbitrary elements.

Examiner traps in Searching

Misreading 'NOT the largest' as 'find the largest' or 'find the second largest' and incorrectly choosing N-1 or N + ⌈ log2 N ⌉ - 2.
Assuming that verifying a property on an unordered list always requires inspecting all N elements.

How questions are asked

Minimum comparisons for property verification on an unordered list

Paper trends

Introduction of conceptual 1-mark questions probing trivial lower bounds and careful reading of problem constraints rather than mechanical formula application.
2025

Difficulty notes

Easy items test simple deduction (e.g., comparing any two distinct elements immediately proves the smaller is not the maximum in 1 comparison). Medium/Hard variants extend to finding elements not in the top- $k$ or median boundaries with adversarial bounds.