Searching

ACompressed recap

🧾

Linear search Θ(n) (best 1, worst n, average (n+1)/2). Binary search on a sorted, randomly accessible array: mid = ⌊(lo+hi)/2⌋, ≤ ⌊log n⌋ + 1 probes, Θ(log n), invariant "x ∈ A[lo..hi] if present"; Θ(n) on linked lists. Variants: first/last occurrence (keep searching left/right on equality), count = last − first + 1, lower bound, rotated arrays, search on a monotone answer. Comparison-based search needs Ω(log n).

BMerged rule card

2.1.1 Linear search and binary search: comparisons and correctness

• Linear search: Θ(n); best 1, worst n, average (n+1)/2.
• Binary search: sorted + random access; ≤ ⌊log n⌋ + 1 probes; Θ(log n); iterative O(1) space.
• Invariant: x, if present, lies in A[lo..hi]. mid = ⌊(lo+hi)/2⌋.
• On a linked list binary search is Θ(n).

2.1.2 Binary search variants and the Ω(log n) lower bound for searching

• First occurrence: equal → record, go left. Last: equal → record, go right. Count = last − first + 1.
• Lower bound: first index with A[i] ≥ x (the final lo).
• Rotated array: one half is sorted at every step.
• Comparison-based search: Ω(log n) (decision tree with ≥ n leaves).

CInterleaved GATE-style questions

Q1NAT1 markProbes

In B = [3, 8, 15, 21, 27, 34, 40, 46, 52, 60, 71], how many probes to find 3?

Numerical answer: ________

Q2NAT1 markMax probes

Maximum probes of binary search on 100 elements?

Numerical answer: ________

Q3NAT2 marksProbes on 31

A sorted array has 31 elements. How many elements need exactly 5 probes to be found?

Numerical answer: ________

Q4MCQ1 markRequirement

Binary search runs in O(log n) only if the data:

• (A) is sorted and stored in an array
• (B) has distinct elements
• (C) is sorted and stored in a linked list
• (D) is a heap

Q5NAT2 marksLast occurrence

A = [2, 4, 4, 4, 7, 9, 9, 12]. Index (0-based) of the last 9?

Numerical answer: ________

Q6NAT1 markLower bound

A = [2, 4, 4, 4, 7, 9, 9, 12]. First index with A[i] ≥ 5?

Numerical answer: ________

Q7MCQ1 markCounting

The fastest way to count occurrences of x in a sorted array of n elements is:

• (A) two binary searches, Θ(log n)
• (B) one binary search then scan both ways, always Θ(log n)
• (C) Θ(n) scan
• (D) hashing all elements first, Θ(1)

Q8NAT2 marksDecision tree

Minimum worst-case comparisons (two-way) to identify the position of a key among 5,000 sorted elements?

Numerical answer: ________

DAnswer Vault