Three Classic Search & Comparison Problems

A. Find Min & Max Efficiently

Given n elements, find both the minimum and maximum using as few comparisons as possible.

Naive Method

Find minimum: n - 1 comparisons
Find maximum: n - 1 comparisons

Total = (n - 1) + (n - 1) = 2n - 2

Key idea: Instead of letting every element compete for both minimum and maximum, first compare elements in pairs.

The smaller element of each pair only needs to compete for the global minimum, while the larger element only needs to compete for the global maximum.

Tournament Pairing

Example:

8 vs 3 11 vs 2 14 vs 6 9 vs 1

After one comparison per pair:

Minimum candidates

3, 2, 6, 1

Maximum candidates

8, 11, 14, 9

For even n:

Pair comparisons: n / 2
Find minimum among the n / 2 smaller elements: n / 2 - 1
Find maximum among the n / 2 larger elements: n / 2 - 1

n/2 + (n/2 - 1) + (n/2 - 1) = 3n/2 - 2

The exact worst-case number of comparisons for arbitrary n is:

ceil(3n / 2) - 2

So instead of approximately 2n comparisons, we need only approximately 1.5n.

B. First Nonzero in an Array of Unknown Length

Suppose an array begins with zeros and then eventually becomes nonzero:

[0, 0, 0, 0, 0, 0, 0, ..., nonzero, nonzero, ...]

We want to find the index of the first nonzero, but we do not know where the transition occurs.

Key idea: We cannot immediately binary search because we do not know the right boundary.

First find a sufficiently large boundary using exponential search. Then use binary search inside that range.

Step 1: Exponential Search

Check indices:

1 → 2 → 4 → 8 → 16 → 32 → ...

Each time the value is still zero, double the index.

Suppose:

A[8] = 0 A[16] != 0

Then the first nonzero must lie somewhere between indices 9 and 16.

Step 2: Binary Search

Now binary search the interval:

[9, 16]

If the middle element is:

0 → move right
nonzero → search the left half, because the first nonzero might be earlier

Complexity

If the first nonzero is at position p, exponential search needs approximately:

log₂(p)

probes.

Binary search also needs:

O(log p)

Therefore:

Total = O(log p)

C. Search a Row- and Column-Sorted Matrix

Suppose every row is sorted from left to right and every column is sorted from top to bottom.

1	4	7	11	15
2	5	8	12	19
3	6	9	16	22
10	13	14	17	24
18	21	23	26	30

Key idea: Start from the top-right corner.

This location is special because moving left makes values smaller, while moving down makes values larger.

Staircase Search

Let the current value be x.

If:

x == target

Found it.

If:

x > target

Move left.

Why? Everything below x in the current column is even larger, so the entire column can be discarded.

If:

x < target

Move down.

Why? Everything to the left of x in the current row is even smaller, so the entire row can be discarded.

Example

Search for:

target = 14

The path is:

15 ↓ because 15 > 14, move left 11 ↓ because 11 < 14, move down 12 ↓ because 12 < 14, move down 16 ↓ because 16 > 14, move left 9 ↓ because 9 < 14, move down 14 ✓ found

Time Complexity

For an m × n matrix:

at most m + n - 1 inspected cells

Therefore:

O(m + n)

For an m × m matrix:

O(m)

Summary

Problem	Main Idea	Complexity
Find min & max	Pair elements first, then run separate min/max tournaments	`⌈3n/2⌉ - 2` comparisons
First nonzero, unknown boundary	Exponential search to find a range, then binary search	`O(log p)`
Search sorted matrix	Start top-right and eliminate one row or column at each step	`O(m + n)`