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

0 · Recall Warm-up

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

• Max probes of binary search on n elements? from Lesson 2.1.1
• T(n) = 2T(n/2) + n? from Lesson 1.2.3
• What does an adjacency list cost in space? from Lesson 0.2.3

1 · The Hook

🎣

"Find the first 4 in [2, 4, 4, 4, 7, 9, 9, 12]" or "how many times does 9 occur?" or "search a sorted array that was rotated". Each is binary search with one line changed. And there is a floor: no comparison-based method can find an element among n with fewer than about log n comparisons.

2 · Predict First

🤔

A = [2, 4, 4, 4, 7, 9, 9, 12]. Plain binary search for 4 probes index 3 first and returns 3. How would you change it to return the first 4 (index 1)?

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

3 · Core Concept

💡

Predict First — the answer

When A[mid] == x, record mid and keep searching left (hi = mid − 1) instead of stopping. The last recorded index is the first occurrence: 1.

First and last occurrence

• First occurrence: on A[mid] == x, set ans = mid, hi = mid − 1.
• Last occurrence: on A[mid] == x, set ans = mid, lo = mid + 1.
• Count of x = last − first + 1, in Θ(log n).

Lower bound (insertion point)

The first index with A[i] ≥ x (where x would be inserted). Same loop: if A[mid] < x, lo = mid + 1, else hi = mid − 1; the answer is lo.

Rotated sorted array

[40, 46, 52, 3, 8, 15, 21] (sorted, then rotated). At each step one half is sorted (compare A[lo] with A[mid]); check whether x lies in that sorted half and discard the other. Still Θ(log n) for distinct elements.

Binary search on the answer

If a yes/no condition is monotone in an integer t (false, …, false, true, …, true), binary search finds the first true t. Example: the integer square root of n = largest t with t² ≤ n.

The Ω(log n) lower bound

A comparison-based search is a decision tree: each comparison splits the possibilities. To distinguish n possible positions you need at least n leaves, and a binary tree of height h has at most 2ʰ leaves. So the worst case needs h ≥ log n comparisons: binary search is optimal.

Interpolation search (brief)

Guess the position from the value (like opening a dictionary near "S" for "S…"). Θ(log log n) on uniformly distributed keys, Θ(n) worst case.

4 · Visual

First occurrence of 4 in A = [2, 4, 4, 4, 7, 9, 9, 12]

lo=0 hi=7 mid=3 A[3]=4  -> ans=3, hi=2
lo=0 hi=2 mid=1 A[1]=4  -> ans=1, hi=0
lo=0 hi=0 mid=0 A[0]=2  -> lo=1
lo=1 > hi=0  stop       -> first = 1

5 · Worked Examples

Example 1 Easy

In A = [2, 4, 4, 4, 7, 9, 9, 12], how many times does 4 occur (first and last occurrence)?

Solution

First 1, last 3 → 3.

Example 2 Medium

Lower bound of x = 8 in A (first index with A[i] ≥ 8)?

Solution

A[5] = 9 is the first ≥ 8 → 5.

Example 3 GATE

What is the minimum worst-case number of comparisons any comparison-based algorithm needs to search a sorted array of 1,000 elements (two-way outcome per comparison, to identify the position)?

Solution

At least ⌈log 1000⌉ = 10: a binary decision tree with 1,000 leaves has height ≥ 10.

6 · GATE Traps

⚠️

• First occurrence: on equality go left; last occurrence: go right.
• Counting occurrences by scanning from one hit is Θ(n) in the worst case; use two binary searches.
• The lower bound is for comparison-based search; hashing (next chapter) is not comparison-based.
• Rotated-array search assumes distinct elements for the Θ(log n) bound.

7 · Memory Hook

🧠

"Found it? Note it and keep going toward the end you want."

8 · Connect the Dots

Chapter 2.1 is complete: search by comparisons is Θ(log n) at best. Chapter 2.2 sidesteps comparisons entirely: hashing computes where a key lives, for expected O(1) search.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markFirst occurrence

A = [1, 3, 3, 3, 3, 5, 8, 8, 10]. Index (0-based) of the first 3?

Numerical answer: ________

Q2NAT2 marksCount

In the same array, how many times does 8 occur, found with first and last occurrence searches?

Numerical answer: ________

Q3NAT1 markLower bound

In the same array, the first index with A[i] ≥ 4?

Numerical answer: ________

Q4MCQ1 markLower bound

Any comparison-based algorithm that searches a sorted array of n elements needs, in the worst case:

• (A) Ω(log n) comparisons
• (B) Ω(n log n) comparisons
• (C) Ω(1) comparisons
• (D) Ω(n) comparisons

Q5MSQ2 marksVariants

Which can be done in O(log n) on a sorted array of n elements?

• (A) Find the smallest element ≥ x
• (B) Print all occurrences of x
• (C) Find the first occurrence of x
• (D) Count occurrences of x

10 · Rule Card

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

11 · Concept Ledger

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

first and last occurrencecounting by two binary searcheslower bound (insertion point)rotated sorted array searchbinary search on the answerdecision-tree lower bound for searchinginterpolation search

12 · Answer Vault