有可能。矩阵
m是大小为 nxn的
方阵。核心思想受到oleg.cherednik的回答的启发。只要我们找到
row的
m，这样`m[row][0]
= val
，我们知道val必须处于行row或row - 1（因为在相同的比较row -
1是false）。因此，我们必须找到我们的候选行（ _O（n）_ ），然后仅分析这两个行（也是 _O（n）_）。如果m不是正方形，而是矩形，则该算法的复杂度为 _O（n + k）_ ，其中 _n_ 是行数， _k_ 是中的列数m`。这导致以下算法。
public class Test { public static boolean contains(final int[][]m, final int value) { int candidateRow = m.length; for (int row = 1; row < m.length; ++row) { if (m[row][0] == value) { return true; } if (m[row][0] > value) { candidateRow = row; break; } } for (int val : m[candidateRow - 1]) { if (val == value) { return true; } } if (candidateRow < m.length) { for (int val : m[candidateRow]) { if (val == value) { return true; } } } return false; } public static void main(String[] args) { int [][] testArray = new int [][]{ { 0, 2, 1, 2, 0, 5, 5, 5 }, { 21, 21, 7, 7, 7, 21, 21, 21 }, { 21, 21, 21, 21, 21, 21, 21, 21 }, { 21, 21, 23, 42, 41, 23, 21, 21 }, { 60, 56, 57, 58, 53, 52, 47, 51 }, { 61, 65, 70, 72, 73, 78, 82, 98 }, { 112, 121, 112, 134, 123, 100, 98, 111 }, { 136, 136, 136, 134, 147, 150, 154, 134 } }; for (int[] row : testArray) { for (int val : row) { System.out.print(contains(testArray, val) + " "); } System.out.println(); } System.out.println(); System.out.println(); final int[] notInMatrix = { -1, 3, 4, 6, 8, 22, 30, 59, 71, 113, 135 }; for (int val : notInMatrix) { System.out.print(contains(testArray, val) + " "); } System.out.println(); }}我们可以通过二进制搜索算法确定候选行，从而在 O（log（n）） 而不是 O（n） 中找到候选行，从而改善手动运行时间。对于平方矩阵，渐近运行时仍为
O（n） ，对于非平方 nxk 矩阵， 仍为 O（log（n）+ k） 。这个想法取自Saeed
Bolhasani的回答
private static int findCandidateRow(final int[][] m, final int value) { int lower = 0; int upper = m.length; int middle = (upper + 1) / 2; while (middle != m.length && middle != 1 && (m[middle][0] < value || m[middle - 1][0] > value)) { if (m[middle][0] < value) { lower = middle; } else { upper = middle; } middle = lower + (upper - lower + 1) / 2; } return middle; }
