搜索算法：三问

Search Algorithms

专题: Algorithmic Programming / 算法编程
难度: L4
来源: QuantQuestion

题目详情

A. 用不超过 $3n/2$ 次比较同时找出 $n$ 个数的最小值与最大值。

B. 一个数组前面全是 0，后面全是非 0，且数组长度未知，如何找到第一个非 0 的索引？

C. 正方形矩阵每行从左到右递增、每列从上到下递增，如何快速判断某个值 $x$ 是否存在？

A. Find min & max from $n$ numbers with $\le 3n/2$ comparisons?

B. Zeropad then all nonzero, size unknown. Find first nonzero index?

C. Square matrix with rows inc left→right, cols inc top→down. Find a target x quickly?

解析

A. 两两配对先比较（ $n/2$ 次），较小者集合找 min（ $n/2-1$ ），较大者集合找 max（ $n/2-1$ ），总计 $\le 3n/2$ 。

B. 先查 1,2,4,8,... 做指数扩张直到命中非 0 的上界 $2^k$ ，再在区间 $[2^{k-1},2^k]$ 二分，复杂度 $O(\log n)$ 。

C. 从右上角开始：若当前值 $>x$ 向左；若 $<x$ 向下。每步排除一行或一列，最多 $2n$ 步，复杂度 $O(n)$ 。

Original Explanation

AnswerA:
Pair up => $\frac{n}{2}$ compares. Smaller half => find min using $\frac{n}{2}-1$ compares. Larger half => find max $\frac{n}{2}-1$ . Total $\le \frac{3n}{2}$ .

AnswerB:
Check index 1,2,4,8,... until find nonzero at $2^k$ . Then do binary search in $[2^{k-1},2^k]$ . Complexity $O(\log n)$ .

AnswerC:
Start top-right. If current> x => go left. If < x => go down. Each step discards a row or col => $\le 2n$ steps. $O(n)$ .