Linear search and binary search: comparisons and correctness

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Θ of T(n) = T(n/2) + 1? from Lesson 1.2.3
• Average comparisons of linear search (present, uniform)? from Lesson 1.3.1
• How many times can you halve n before reaching 1? from Lesson 0.1.2

1 · The Hook

🎣

Find a name in a phone book of a million entries. Reading page by page takes up to a million looks; opening the middle and throwing away half each time takes 20. That is binary search, the first algorithm in the GATE syllabus and the model for every "halve the problem" idea that follows.

2 · Predict First

🤔

Sorted array B = [3, 8, 15, 21, 27, 34, 40, 46, 52, 60, 71] (indices 0–10). Binary search for 52, always probing index mid = ⌊(lo + hi)/2⌋. Which elements are probed?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

mid = 5 → 34 (52 is bigger, go right: lo = 6); mid = 8 → 52: found after 2 probes.

Linear search

Scan left to right. Works on any array (sorted or not). Comparisons: best 1, worst n (or n for an unsuccessful search), average (n + 1)/2 when present (Lesson 1.3.1). Θ(n).

Binary search (array sorted ascending)

int bsearch(int A[], int n, int x) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (A[mid] == x) return mid;
        if (A[mid] < x) lo = mid + 1;
        else            hi = mid - 1;
    }
    return -1;              // not found
}

• Invariant: if x is in A, it is in A[lo..hi].
• Each probe halves the range: at most ⌊log n⌋ + 1 probes. T(n) = T(n/2) + c → Θ(log n).
• Needs random access: on a linked list, reaching the middle costs Θ(n), so binary search loses its advantage.
• Recursive version uses O(log n) stack; iterative uses O(1).

Counting probes

"Probes" = loop iterations (each compares x with A[mid]). For n = 11 the maximum is ⌊log 11⌋ + 1 = 4.

The search path

Every search follows a path in a fixed decision tree: the root is the first mid, its children are the mids of the left and right halves, and so on. Elements at depth d need d + 1 probes.

4 · Visual

B:  [3, 8, 15, 21, 27, 34, 40, 46, 52, 60, 71]
idx  0  1   2   3   4   5   6   7   8   9  10

Decision tree of probes (index: value)
                    5:34
               /           \
           2:15             8:52
          /    \           /    \
       0:3     3:21     6:40    9:60
         \        \        \       \
         1:8     4:27     7:46    10:71

5 · Worked Examples

Example 1 Easy

In B, which elements are probed when searching for 46?

Solution

34 → 52 → 40 → 46 (4 probes).

Example 2 Medium

In B, search for 10 (not present). Which elements are probed?

Solution

34 → 15 → 3 → 8; then lo > hi: 4 probes, return −1.

Example 3 GATE

What is the maximum number of probes binary search makes on a sorted array of 1,000 elements?

Solution

⌊log 1000⌋ + 1 = 9 + 1 = 10.

6 · GATE Traps

⚠️

• Binary search needs a sorted array with random access.
• Worst-case probes = ⌊log n⌋ + 1, not ⌈log n⌉ (they differ for powers of two: n = 1024 → 11).
• mid uses the floor of (lo + hi)/2 unless stated.
• Unsuccessful searches also cost up to ⌊log n⌋ + 1 probes.

7 · Memory Hook

🧠

"Look in the middle, throw away half."

8 · Connect the Dots

Phase 1 gave the tools; this lesson applied them to the first syllabus topic. Next: binary search variants (first occurrence, rotated arrays) and why no comparison-based search can beat log n.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markProbes

How many probes does binary search make to find 21 in B?

Numerical answer: ________

Q2NAT1 markMax probes

Maximum probes of binary search on 1,024 sorted elements?

Numerical answer: ________

Q3NAT2 marksProbe sequence

In B, how many probes for an unsuccessful search for 100?

Numerical answer: ________

Q4MCQ1 markLinked list

Binary search on a sorted singly linked list of n nodes takes:

• (A) Θ(log n)
• (B) Θ(1)
• (C) Θ(n log n)
• (D) Θ(n)

Q5MSQ2 marksFacts

Which are true?

• (A) Binary search's worst case is Θ(log n).
• (B) Iterative binary search uses O(1) extra space.
• (C) Binary search needs the array to be sorted.
• (D) Linear search requires a sorted array.

10 · Rule Card

• 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).

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

linear searchbinary searchsearch invariantprobe count ⌊log n⌋ + 1binary-search decision treerandom access requirement

12 · Answer Vault