chapter

Searching Algorithms and Binary Search Short Notes for GATE DA

Searching Algorithms and Binary Search short notes for GATE DA: 2 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice ques

searching algorithms and binary search short notes

Quick Recall: Binary Search Worst-Case

Quick Recall: Worst-Case Concept Formula / Rule Recurrence Relation T (n) = T (⌊ n /2 ⌋) + c Exact Max Comparisons ⌊ lo g_{2} n ⌋ + 1 Found vs Not Found Worst-case depth is identical. Comparisons per Step Check if 1 (3-way) or 2 (if-else). Halve the size, add one step, take the floor of the log, and never forget the plus one.

Quick Recall: Preconditions & Representation

Quick Recall: Preconditions Requirement Reason Consequence if Missing Sorted Order Enables elimination principle. Cannot discard half ⟹ O (n) Random Access Enables O (1) mid calculation. Cannot jump to mid ⟹ collapse Contiguous Memory Arrays provide direct indexing. Linked lists require O (n) traversal Sorting allows elimination. Contiguous memory allows instant jumps. You need both for O (lo g n) .

Try a question

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

Question 1

Level 1: Warm-up

In a binary search implementation, each step checks if the middle element is equal to the target, and if not, checks if it is less than the target. For an array of size N, which of the following statements is true regarding the maximum number of comparisons?

Question 2

Level 1: Warm-up

For a standard binary search, which of the following array sizes N makes it impossible for the maximum number of comparisons to be exactly 5?

Question 3

Level 1: Warm-up

Consider a recursive binary search on an array of size N = 100 . The implementation uses separate checks for equality and inequality at each step. Which of the following statements correctly describes the worst-case number of comparisons M ?

Question 4

Level 1: Warm-up

For a standard binary search, which of the following array sizes N makes it impossible for the maximum number of comparisons to be exactly 8?

Question 5

Level 1: Warm-up

Consider a recursive binary search on an array of size N = 250 . The implementation uses separate checks for equality and inequality at each step. Which of the following statements correctly describes the worst-case number of comparisons M ?

Question 6

Level 1: Warm-up

For a standard binary search, which of the following array sizes N makes it impossible for the maximum number of comparisons to be exactly 9?

Question 7

Level 1: Warm-up

Consider a recursive binary search on an array of size N = 60 . The implementation uses separate checks for equality and inequality at each step. Which of the following statements correctly describes the worst-case number of comparisons M ?

Question 8

Level 1: Warm-up

For a standard binary search, which of the following array sizes N makes it impossible for the maximum number of comparisons to be exactly 10?

Question 9

Level 1: Warm-up

Consider a recursive binary search on an array of size N = 150 . The implementation uses separate checks for equality and inequality at each step. Which of the following statements correctly describes the worst-case number of comparisons M ?

Question 10

Level 1: Warm-up

For a standard binary search on a sorted array with duplicate elements, which of the following actions makes it impossible to guarantee finding the first occurrence of the target in O (lo g n) time?

Free preview ends here

Login to view the complete short notes

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 Short Notes for GATE DA

Searching Algorithms and Binary Search short notes for GATE DA: 2 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Quick Recall: Binary Search Worst-Case

Quick Recall: Worst-Case

Concept	Formula / Rule
Recurrence Relation	$T (n) = T (⌊ n /2 ⌋) + c$
Exact Max Comparisons	$⌊ lo g_{2} n ⌋ + 1$
Found vs Not Found	Worst-case depth is identical.
Comparisons per Step	Check if 1 (3-way) or 2 (if-else).

Halve the size, add one step,
take the floor of the log, and never forget the plus one.

Quick Recall: Preconditions & Representation

Quick Recall: Preconditions

Requirement	Reason	Consequence if Missing
Sorted Order	Enables elimination principle.	Cannot discard half $⟹ O (n)$
Random Access	Enables $O (1)$ mid calculation.	Cannot jump to mid $⟹$ collapse
Contiguous Memory	Arrays provide direct indexing.	Linked lists require $O (n)$ traversal

Sorting allows elimination. Contiguous memory allows instant jumps. You need both for $O (lo g n)$ .

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

Question 1 · Programming, Data Structures and Algorithms MCQ

In a binary search implementation, each step checks if the middle element is equal to the target, and if not, checks if it is less than the target. For an array of size $N$ , which of the following statements is true regarding the maximum number of comparisons?

A.
It is bounded by $⌊ lo g_{2} N f l oor + 1$
B.
It is bounded by $2 ⌊ lo g_{2} N f l oor + 2$
C.
It is bounded by $⌈ lo g_{2} N ce i l$
D.
It is bounded by $2 ⌈ lo g_{2} N ce i l$

Correct Answer:

Step-by-Step Solution

Key idea: This tests the comparison counting trap based on code implementation.

Step 1: Analyze the code logic. There are two comparisons per step: one for equality, one for less-than.

Step 2: The depth of the tree is still $⌊ lo g_{2} N ⌋ + 1$ .

Step 3: Multiply the depth by the number of comparisons per step: $2 \times (⌊ lo g_{2} N ⌋ + 1) = 2 ⌊ lo g_{2} N ⌋ + 2$ .

Answer: It is bounded by $2 ⌊ lo g_{2} N ⌋ + 2$ .

Question 2 · Programming, Data Structures and Algorithms MCQ

For a standard binary search, which of the following array sizes $N$ makes it impossible for the maximum number of comparisons to be exactly 5?

A.
16
B.
20
C.
15
D.
31

Correct Answer:

Step-by-Step Solution

Key idea: This tests the boundary cases of the floor function in the formula.

Step 1: Set the formula equal to 5: $⌊ lo g_{2} N ⌋ + 1 = 5$ .

Step 2: Solve for the floor: $⌊ lo g_{2} N ⌋ = 4$ .

Step 3: Convert to an inequality: $4 \leq lo g_{2} N < 5$ , which means $2^{4} \leq N < 2^{5}$ , or $16 \leq N \leq 31$ .

Step 4: Check the options. 16, 20, and 31 are all in the range $[16, 31]$ .

Step 5: 15 is outside this range, making it impossible.

Answer: 15

Question 3 · Programming, Data Structures and Algorithms MCQ

Consider a recursive binary search on an array of size $N = 100$ . The implementation uses separate checks for equality and inequality at each step. Which of the following statements correctly describes the worst-case number of comparisons $M$ ?

A.
$M$ is strictly less than 14
B.
$M$ is bounded above by 14
C.
$M$ is exactly 13
D.
$M$ is bounded above by 13

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question that tests the comparison counting trap with a specific array size.

Step 1: Identify $N = 100$ and the comparison type (separate checks = 2 comparisons per step).

Step 2: Calculate the tree depth: $⌊ lo g_{2} 100 ⌋ + 1$ . Since $2^{6} = 64$ and $2^{7} = 128$ , $⌊ lo g_{2} 100 ⌋ = 6$ .

Step 3: Depth = $6 + 1 = 7$ .

Step 4: Calculate the worst-case comparisons: $2 \times 7 = 14$ .

Step 5: Evaluate the options. $M$ can be exactly 14 in the worst case. Therefore, " $M$ is bounded above by 14" is the only true statement.

Answer: $M$ is bounded above by 14.

Question 4 · Programming, Data Structures and Algorithms MCQ

For a standard binary search, which of the following array sizes $N$ makes it impossible for the maximum number of comparisons to be exactly 8?

A.
128
B.
200
C.
255
D.
256

Correct Answer:

Step-by-Step Solution

Key idea: This tests the boundary cases of the floor function in the formula.

Step 1: Set the formula equal to 8: $⌊ lo g_{2} N ⌋ + 1 = 8$ .

Step 2: Solve for the floor: $⌊ lo g_{2} N ⌋ = 7$ .

Step 3: Convert to an inequality: $7 \leq lo g_{2} N < 8$ , which means $2^{7} \leq N < 2^{8}$ , or $128 \leq N \leq 255$ .

Step 4: Check the options. 128, 200, and 255 are all in the range $[128, 255]$ .

Step 5: 256 is outside this range, making it impossible.

Answer: 256

Question 5 · Programming, Data Structures and Algorithms MCQ

Consider a recursive binary search on an array of size $N = 250$ . The implementation uses separate checks for equality and inequality at each step. Which of the following statements correctly describes the worst-case number of comparisons $M$ ?

A.
$M$ is strictly less than 16
B.
$M$ is bounded above by 16
C.
$M$ is exactly 15
D.
$M$ is bounded above by 15

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question that tests the comparison counting trap with a specific array size.

Step 1: Identify $N = 250$ and the comparison type (separate checks = 2 comparisons per step).

Step 2: Calculate the tree depth: $⌊ lo g_{2} 250 ⌋ + 1$ . Since $2^{7} = 128$ and $2^{8} = 256$ , $⌊ lo g_{2} 250 ⌋ = 7$ .

Step 3: Depth = $7 + 1 = 8$ .

Step 4: Calculate the worst-case comparisons: $2 \times 8 = 16$ .

Step 5: Evaluate the options. $M$ can be exactly 16 in the worst case. Therefore, " $M$ is bounded above by 16" is the only true statement.

Answer: $M$ is bounded above by 16.

Question 6 · Programming, Data Structures and Algorithms MCQ

For a standard binary search, which of the following array sizes $N$ makes it impossible for the maximum number of comparisons to be exactly 9?

A.
256
B.
300
C.
511
D.
512

Correct Answer:

Step-by-Step Solution

Key idea: This tests the boundary cases of the floor function in the formula.

Step 1: Set the formula equal to 9: $⌊ lo g_{2} N ⌋ + 1 = 9$ .

Step 2: Solve for the floor: $⌊ lo g_{2} N ⌋ = 8$ .

Step 3: Convert to an inequality: $8 \leq lo g_{2} N < 9$ , which means $2^{8} \leq N < 2^{9}$ , or $256 \leq N \leq 511$ .

Step 4: Check the options. 256, 300, and 511 are all in the range $[256, 511]$ .

Step 5: 512 is outside this range, making it impossible.

Answer: 512

Question 7 · Programming, Data Structures and Algorithms MCQ

Consider a recursive binary search on an array of size $N = 60$ . The implementation uses separate checks for equality and inequality at each step. Which of the following statements correctly describes the worst-case number of comparisons $M$ ?

A.
$M$ is strictly less than 12
B.
$M$ is bounded above by 12
C.
$M$ is exactly 11
D.
$M$ is bounded above by 11

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question that tests the comparison counting trap with a specific array size.

Step 1: Identify $N = 60$ and the comparison type (separate checks = 2 comparisons per step).

Step 2: Calculate the tree depth: $⌊ lo g_{2} 60 ⌋ + 1$ . Since $2^{5} = 32$ and $2^{6} = 64$ , $⌊ lo g_{2} 60 ⌋ = 5$ .

Step 3: Depth = $5 + 1 = 6$ .

Step 4: Calculate the worst-case comparisons: $2 \times 6 = 12$ .

Step 5: Evaluate the options. $M$ can be exactly 12 in the worst case. Therefore, " $M$ is bounded above by 12" is the only true statement.

Answer: $M$ is bounded above by 12.

Question 8 · Programming, Data Structures and Algorithms MCQ

For a standard binary search, which of the following array sizes $N$ makes it impossible for the maximum number of comparisons to be exactly 10?

A.
512
B.
750
C.
1023
D.
1024

Correct Answer:

Step-by-Step Solution

Key idea: This tests the boundary cases of the floor function in the formula.

Step 1: Set the formula equal to 10: $⌊ lo g_{2} N ⌋ + 1 = 10$ .

Step 2: Solve for the floor: $⌊ lo g_{2} N ⌋ = 9$ .

Step 3: Convert to an inequality: $9 \leq lo g_{2} N < 10$ , which means $2^{9} \leq N < 2^{10}$ , or $512 \leq N \leq 1023$ .

Step 4: Check the options. 512, 750, and 1023 are all in the range $[512, 1023]$ .

Step 5: 1024 is outside this range, making it impossible.

Answer: 1024.

Question 9 · Programming, Data Structures and Algorithms MCQ

Consider a recursive binary search on an array of size $N = 150$ . The implementation uses separate checks for equality and inequality at each step. Which of the following statements correctly describes the worst-case number of comparisons $M$ ?

A.
$M$ is strictly less than 16
B.
$M$ is bounded above by 16
C.
$M$ is exactly 15
D.
$M$ is bounded above by 15

Correct Answer:

Step-by-Step Solution

Key idea: This is a bounding question that tests the comparison counting trap with a specific array size.

Step 1: Identify $N = 150$ and the comparison type (separate checks = 2 comparisons per step).

Step 2: Calculate the tree depth: $⌊ lo g_{2} 150 ⌋ + 1$ . Since $2^{7} = 128$ and $2^{8} = 256$ , $⌊ lo g_{2} 150 ⌋ = 7$ .

Step 3: Depth = $7 + 1 = 8$ .

Step 4: Calculate the worst-case comparisons: $2 \times 8 = 16$ .

Step 5: Evaluate the options. $M$ can be exactly 16 in the worst case. Therefore, " $M$ is bounded above by 16" is the only true statement.

Answer: $M$ is bounded above by 16.

Question 10 · Programming, Data Structures and Algorithms MCQ

For a standard binary search on a sorted array with duplicate elements, which of the following actions makes it impossible to guarantee finding the first occurrence of the target in $O (lo g n)$ time?

A.
Continuing the search in the left half after a match
B.
Returning the index immediately upon finding a match
C.
Using linear search from the beginning of the array
D.
Sorting the array in descending order before searching

Correct Answer:

Step-by-Step Solution

Key idea: This tests the boundary case of handling duplicates and the modification required to find the first occurrence.

Step 1: Understand the goal. We want the first occurrence of the target in $O (lo g n)$ time.

Step 2: Evaluate Option A. Continuing the search in the left half after a match is the correct modification to push the search towards the first occurrence. It maintains $O (lo g n)$ .

Step 3: Evaluate Option B. Returning the index immediately upon finding a match stops the search at an arbitrary occurrence. It makes it impossible to guarantee finding the first occurrence.

Step 4: Evaluate Option C. Using linear search degrades the time complexity to $O (n)$ , violating the $O (lo g n)$ constraint, but the question asks what makes it impossible to guarantee finding the first occurrence in $O (lo g n)$ time via the binary search logic itself. Wait, returning immediately is the fundamental flaw in the standard algorithm for this specific goal.

Step 5: Evaluate Option D. Sorting in descending order just flips the comparison logic; it doesn't solve the duplicate boundary issue.

Step 6: The action that breaks the guarantee of finding the first occurrence while attempting to maintain the search logic is returning immediately.

Answer: Returning the index immediately upon finding a match.

searching algorithms and binary search short notes

Quick Recall: Binary Search Worst-Case

Quick Recall: Worst-Case

Quick Recall: Preconditions & Representation

Quick Recall: Preconditions

Try a question

Login to view the complete short notes

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 Short Notes for GATE DA

Quick Recall: Binary Search Worst-Case

Quick Recall: Worst-Case

Quick Recall: Preconditions & Representation

Quick Recall: Preconditions

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

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More short notes in this unit