Sorted Matrix

Definition / 释义

sorted matrix（有序矩阵；排序矩阵）：指矩阵（二维数组）中的元素按某种规则“有序”排列，常见的是每一行按升序排列，并且有时还要求每一列也按升序排列（具体约束取决于题目或语境）。该概念常用于算法与数据结构中，便于进行高效查找（如二分查找或“从角落走”的搜索）。

Pronunciation (IPA) / 发音（IPA）

/ˈsɔːrtɪd ˈmeɪtrɪks/

Examples / 例句

A sorted matrix makes searching faster.
有序矩阵能让查找更快。

Given a sorted matrix where each row and column is increasing, you can find the target in linear time by scanning from the top-right corner.
在一个行与列都递增的有序矩阵中，你可以从右上角开始扫描，用线性时间找到目标值。

Etymology / 词源

sorted 来自动词 sort（“整理、分类、排序”），与“把事物按规则排好”有关；matrix 源自拉丁语 matrix（本义与“母体/来源”相关），在数学中引申为“用于组织与表示数值的表格结构”。组合成 sorted matrix，即“元素已按规则排序的矩阵”。

Related Words / 相关词汇

• Array
• Matrix
• Sorted
• Order
• Ascending
• Descending
• Binary Search
• Search
• Algorithm
• Monotonic

Notable Works / 作品与文献中的用例

• Thomas H. Cormen et al., Introduction to Algorithms（《算法导论》）：在“查找、排序、数据结构”相关章节中常讨论有序结构（包括二维数组/矩阵的变体）用于加速搜索。
• Donald E. Knuth, The Art of Computer Programming（《计算机程序设计艺术》）：涉及排序与查找理论，常以多种数据组织形式（含二维结构的讨论）说明算法思想。
• Jon Bentley, Programming Pearls（《编程珠玑》）：以问题驱动方式讨论“如何利用有序性提高查找效率”，与有序矩阵类题目思路高度相关。