我最近接受了这个面试问题，我很好奇它是一个很好的解决方案。
假设我有一个二维数组，其中数组中的所有数字从左到右，从上到下依次递增。
搜索和确定目标号码是否在阵列中的最佳方法是什么？
现在，我的第一个倾向是利用二进制搜索，因为我的数据已经排序。我可以确定O（log N）时间内的数字是否在一行中。然而，正是这两个方向让我失望。
我认为可能有用的另一种解决方案是从中间的某个地方开始。如果中间值小于我的目标，那么我可以确定它在中间的矩阵的左方形部分。然后我沿着对角线移动并再次检查，减小了目标可能存在的方格的大小，直到我对目标数字进行了磨练。
有没有人有解决这个问题的好主意？
示例数组：
从左到右，从上到下排序。
1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11
这是一个简单的方法：
对于NxM阵列，这在O(N+M)中运行。我认为要做得更好很难。 :)
编辑：很多很好的讨论。我在谈论上面的一般情况;很明显，如果N或M很小，你可以使用二进制搜索方法在接近对数时间的情况下执行此操作。
以下是一些细节，对于那些好奇的人：
这个简单的算法称为Saddleback Search。它已经存在了一段时间，当N == M时它是最佳的。一些参考：
但是，当The Saddleback Search，直觉表明二进制搜索应该能够比N < M做得更好：例如，当O(N+M)时，纯二进制搜索将以对数而不是线性时间运行。
理查德·伯德（Richard Bird）研究了这种直觉，二元搜索可以在2006年的论文中改进Saddleback算法：
N == 1，“程序建设数学”，第82-89页，第4014卷，2006年。使用一种相当不寻常的会话技术，Bird告诉我们，对于Improving Saddleback Search: A Lesson in Algorithm Design，这个问题具有N <= M的下限。这个界限是有意义的，因为当Ω(N * log(M/N))和N == M时的对数性能时，它给出了线性性能。
一种使用逐行二进制搜索的方法如下所示：
N == 1的矩形阵列开始。让我们说N < M是行，N是列。M的中间行进行二分查找。如果我们找到它，我们就完成了。value和s，其中g。s < value < g上方和左侧的数字矩形小于s，因此我们可以消除它。value下方和右侧的矩形大于g，因此我们可以消除它。就最坏情况复杂性而言，该算法使value能够消除一半可能的解决方案，然后在两个较小的问题上递归调用两次。我们必须为每一行重复该log(M)工作的较小版本，但如果行数与列数相比较小，那么能够在对数时间内消除所有这些列开始变得值得。
这给了算法log(M)的复杂性，Bird显示为T(N,M) = log(M) + 2 * T(M/2, N/2)。
O(N * log(M/N))描述了一种类似于上述方法的算法：它使用步长Another approach posted by Craig Gidney一次检查一行。他的分析表明，这也导致了M/N的表现。
Big-O分析一切都很好，但这些方法在实践中的效果如何？下面的图表检查了越来越“方形”数组的四种算法：
（“天真”算法只是搜索数组的每个元素。“递归”算法如上所述。“混合”算法是O(N * log(M/N))的实现。对于每个数组大小，性能是通过在固定集合上对每个算法进行计时来测量的。 1,000,000个随机生成的数组。）
一些值得注意的要点：
巧妙地使用二进制搜索可以为矩形和方形阵列提供Gidney's algorithm性能。 O(N * log(M/N)“saddleback”算法要简单得多，但随着阵列变得越来越矩形，性能会下降。
二进制搜索将是最好的方法，imo。从1/2 x开始，1/2 y将其切成两半。 IE 5x5平方就像x == 2 / y == 3。我将一个值向下舍入，将一个值向上舍入到目标值方向的更好区域。
为清楚起见，下一次迭代会给你类似x == 1 / y == 2 OR x == 3 / y == 5
好吧，首先，让我们假设我们正在使用一个正方形。
bool findNum(int arr[][ARR_MAX],int xmin, int xmax, int ymin,int ymax,int key)
{
if (xmin > xmax || ymin > ymax || xmax < xmin || ymax < ymin) return false;
if ((xmin == xmax) && (ymin == ymax) && (arr[xmin][ymin] != key)) return false;
if (arr[xmin][ymin] > key || arr[xmax][ymax] < key) return false;
if (arr[xmin][ymin] == key || arr[xmax][ymax] == key) return true;
int xnew = (xmin + xmax)/2;
int ynew = (ymin + ymax)/2;
if (arr[xnew][ynew] == key) return true;
if (arr[xnew][ynew] < key)
{
if (findNum(arr,xnew+1,xmax,ymin,ymax,key))
return true;
return (findNum(arr,xmin,xmax,ynew+1,ymax,key));
} else {
if (findNum(arr,xmin,xnew-1,ymin,ymax,key))
return true;
return (findNum(arr,xmin,xmax,ymin,ynew-1,key));
}
}
1.搜索正方形
我会在对角线上使用二分搜索。目标是找到不严格低于目标数量的较小数字。
比如说我正在寻找1 2 3
2 3 4
3 4 5
，然后我最终会在4找到5。
然后，我确信如果(2,2)在表中，它位于4或(x,2)的(2,x)的x或[0,2]。好吧，这只是2个二进制搜索。
复杂性并不令人生畏：O(log(N))（长度为N的3个二进制搜索）
2.搜索矩形，天真的方法
当然，当N和M不同（带有矩形）时，它会变得有点复杂，请考虑这种退化情况：
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17
让我们说我正在寻找9 ...对角线方法仍然很好，但对角线的变化定义。在这里，我的对角线是[1, (5 or 6), 17]。假设我选择了[1,5,17]，然后我知道如果9在表中，则它在子部分中：
5 6 7 8
6 7 8 9
10 11 12 13 14 15 16
这给了我们2个矩形：
5 6 7 8 10 11 12 13 14 15 16
6 7 8 9
所以我们可以递归！可能从具有较少元素的那个开始（尽管在这种情况下它会杀死我们）。
我应该指出，如果其中一个维度小于3，我们就不能应用对角线方法，必须使用二进制搜索。这意味着：
10 11 12 13 14 15 16上应用二进制搜索，未找到5 6 7 8上应用二进制搜索，未找到6 7 8 9上应用二进制搜索，未找到这很棘手，因为要获得良好的性能，您可能希望区分几种情况，具体取决于一般形状....
3.搜索矩形，残酷的方法
如果我们处理一个正方形会更容易......所以让我们把事情放在一边。
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17
17 . . . . . . 17
. .
. .
. .
17 . . . . . . 17
我们现在有一个广场。
当然，我们可能不会实际创建那些行，我们可以简单地模拟它们。
def get(x,y):
if x < N and y < M: return table[x][y]
else: return table[N-1][M-1] # the max
所以它的行为就像一个正方形而没有占用更多的内存（以速度为代价，可能，取决于缓存...哦，好吧：p）
编辑：
我误解了这个问题。正如评论所指出的那样，这只适用于更受限制的情况。
在像C这样的语言中，以行主要顺序存储数据，只需将其视为大小为n * m的一维数组，并使用二进制搜索。
我有一个递归的Divide＆Conquer解决方案。一步的基本思路是：我们知道左上（LU）最小而右下（RB）是最大的数字，因此给定的否（N）必须：N> = LU和N <= RB
如果N == LU和N == RB ::::元素找到并且中止返回位置/索引如果N> = LU并且N <= RB = FALSE，则不存在并且中止。如果N> = LU且N <= RB = TRUE，则以逻辑方式将2D阵列分成4个相等的2D阵列部分。然后将相同的算法步骤应用于所有四个子阵列。
我的Algo是正确的我已经在我的朋友PC上实现了。复杂性：在最坏的情况下，每4次比较可以用来推断元素的总数不到四分之一。所以我的复杂性变为1 + 4 x lg（n）+ 4但是真的希望这是在O上工作（n）的
在我的复杂度计算中，我认为某些地方出了问题，如果是这样，请更正..
最佳解决方案是从左上角开始，它具有最小的价值。沿对角线向下向右移动，直到您点击一个值> =给定元素值的元素。如果元素的值等于给定元素的值，则返回find为true。
否则，从这里我们可以以两种方式进行。
策略1：
策略2：让我表示行索引，j表示我们已经停止的对角元素的列索引。 （这里，我们有i = j，BTW）。设k = 1。
1 2 4 5 6 2 3 5 7 8 4 6 8 9 10 5 8 9 10 11
public boolean searchSortedMatrix(int arr[][] , int key , int minX , int maxX , int minY , int maxY){
// base case for recursion
if(minX > maxX || minY > maxY)
return false ;
// early fails
// array not properly intialized
if(arr==null || arr.length==0)
return false ;
// arr[0][0]> key return false
if(arr[minX][minY]>key)
return false ;
// arr[maxX][maxY]<key return false
if(arr[maxX][maxY]<key)
return false ;
//int temp1 = minX ;
//int temp2 = minY ;
int midX = (minX+maxX)/2 ;
//if(temp1==midX){midX+=1 ;}
int midY = (minY+maxY)/2 ;
//if(temp2==midY){midY+=1 ;}
// arr[midX][midY] = key ? then value found
if(arr[midX][midY] == key)
return true ;
// alas ! i have to keep looking
// arr[midX][midY] < key ? search right quad and bottom matrix ;
if(arr[midX][midY] < key){
if( searchSortedMatrix(arr ,key , minX,maxX , midY+1 , maxY))
return true ;
// search bottom half of matrix
if( searchSortedMatrix(arr ,key , midX+1,maxX , minY , maxY))
return true ;
}
// arr[midX][midY] > key ? search left quad matrix ;
else {
return(searchSortedMatrix(arr , key , minX,midX-1,minY,midY-1));
}
return false ;
}
我建议，将所有字符存储在2D list中。然后找到所需元素的索引（如果它存在于列表中）。
如果不存在则打印相应的消息，否则打印行和列为：
row = (index/total_columns)和column = (index%total_columns -1)
这将仅在列表中产生二进制搜索时间。
请提出任何更正建议。 :)
如果O（M log（N））解决方案适用于MxN阵列 -
template <size_t n>
struct MN * get(int a[][n], int k, int M, int N){
struct MN *result = new MN;
result->m = -1;
result->n = -1;
/* Do a binary search on each row since rows (and columns too) are sorted. */
for(int i = 0; i < M; i++){
int lo = 0; int hi = N - 1;
while(lo <= hi){
int mid = lo + (hi-lo)/2;
if(k < a[i][mid]) hi = mid - 1;
else if (k > a[i][mid]) lo = mid + 1;
else{
result->m = i;
result->n = mid;
return result;
}
}
}
return result;
}
如果这不起作用或者如果有错误，请告诉我。
给定方阵如下：
[ a b c ] [ d e f ] [ i j k ]
我们知道a <c，d <f，i <k。我们不知道的是d <c还是d> c等。我们只有一维保证。
查看结束元素（c，f，k），我们可以做一种过滤：N <c？ search（）：next（）。因此，我们对行进行了n次迭代，每行采用O（log（n））进行二进制搜索，如果滤出则采用O（1）。
让我举个例子，其中N = j，
1）检查第1行.j <c？ （不，下一步）
2）检查第2行.j <f？ （是的，bin搜索什么都没有）
3）检查第3行.j <k？ （是的，bin搜索找到它）
再试N = q，
1）检查第1行.q <c？ （不，下一步）
2）检查第2行.q <f？ （不，下一步）
3）检查第3行.q <k？ （不，下一步）
可能有一个更好的解决方案，但这很容易解释.. :)
由于这是一个采访问题，它似乎引出了对并行编程和Map-reduce算法的讨论。
见http://code.google.com/intl/de/edu/parallel/mapreduce-tutorial.html
这个问题需要O(N + M)时间，其中Θ(b lg(t))和b = min(w,h)。我在t=b/max(w,h)讨论解决方案。
下限
攻击者可以强制算法通过将自身限制在主对角线来进行this blog post查询：
图例：白色单元格较小，灰色单元格较大，黄色单元格较小或相等，橙色单元格较大或相等。攻击者强制解决方案是算法查询的最后一个黄色或橙色单元格。
请注意，有Ω(b lg(t))独立排序列表的大小b，要求t查询完全消除。
算法
Ω(b lg(t))）w >= h进行比较
如果单元格的项目匹配，则返回当前位置。
如果单元格的项目小于目标项目，则使用二进制搜索消除行中剩余的t单元格。如果在执行此操作时找到匹配项，请返回其位置。
否则，单元格的项目超过目标项目，从而消除了t短列。寻找物品：
确定项目不存在：
图例：白色单元格较小，灰色单元格较大，绿色单元格相同。
分析
有t短列可以消除。有b*t长行消除。消除长排费用b时间。消除O(lg(t))短柱需要花费t时间。
在最坏的情况下，我们必须消除每一列和每一行，花费时间O(1)。
请注意，我假设O(lg(t)*b + b*t*1/t) = O(b lg(t))钳位到1以上的结果（即lg）。这就是为什么当lg(x) = log_2(max(2,x))，意思是w=h，我们得到t=1的预期界限。
码
O(b lg(1)) = O(b) = O(w+h)我会对这个问题使用分而治之的策略，类似于你的建议，但细节有点不同。
这将是对矩阵子范围的递归搜索。
在每个步骤中，选择范围中间的元素。如果找到的值是您正在寻找的，那么您就完成了。
否则，如果找到的值小于您要搜索的值，则表示它不在您当前位置的上方和左侧的象限中。因此，递归搜索两个子范围：当前位置下方的所有内容（专有），以及当前位置或其上方的所有内容（仅限于）。
否则，（找到的值大于您要搜索的值）您知道它不在您当前位置下方和右侧的象限中。因此，递归搜索两个子范围：当前位置左侧的所有内容（排他性），以及当前列上当前位置或右侧列上的所有内容（排他地）。
巴德达，你找到了它。
请注意，每个递归调用仅处理当前子范围，而不是（例如）当前位置上方的所有行。只是当前子范围内的那些。
这是你的一些伪代码：
public static Tuple<int, int> TryFindItemInSortedMatrix<T>(this IReadOnlyList<IReadOnlyList<T>> grid, T item, IComparer<T> comparer = null) {
if (grid == null) throw new ArgumentNullException("grid");
comparer = comparer ?? Comparer<T>.Default;
// check size
var width = grid.Count;
if (width == 0) return null;
var height = grid[0].Count;
if (height < width) {
var result = grid.LazyTranspose().TryFindItemInSortedMatrix(item, comparer);
if (result == null) return null;
return Tuple.Create(result.Item2, result.Item1);
}
// search
var minCol = 0;
var maxRow = height - 1;
var t = height / width;
while (minCol < width && maxRow >= 0) {
// query the item in the minimum column, t above the maximum row
var luckyRow = Math.Max(maxRow - t, 0);
var cmpItemVsLucky = comparer.Compare(item, grid[minCol][luckyRow]);
if (cmpItemVsLucky == 0) return Tuple.Create(minCol, luckyRow);
// did we eliminate t rows from the bottom?
if (cmpItemVsLucky < 0) {
maxRow = luckyRow - 1;
continue;
}
// we eliminated most of the current minimum column
// spend lg(t) time eliminating rest of column
var minRowInCol = luckyRow + 1;
var maxRowInCol = maxRow;
while (minRowInCol <= maxRowInCol) {
var mid = minRowInCol + (maxRowInCol - minRowInCol + 1) / 2;
var cmpItemVsMid = comparer.Compare(item, grid[minCol][mid]);
if (cmpItemVsMid == 0) return Tuple.Create(minCol, mid);
if (cmpItemVsMid > 0) {
minRowInCol = mid + 1;
} else {
maxRowInCol = mid - 1;
maxRow = mid - 1;
}
}
minCol += 1;
}
return null;
}
到目前为止，两个主要答案似乎是可以说是bool numberSearch(int[][] arr, int value, int minX, int maxX, int minY, int maxY)
if (minX == maxX and minY == maxY and arr[minX,minY] != value)
return false
if (arr[minX,minY] > value) return false; // Early exits if the value can't be in
if (arr[maxX,maxY] < value) return false; // this subrange at all.
int nextX = (minX + maxX) / 2
int nextY = (minY + maxY) / 2
if (arr[nextX,nextY] == value)
{
print nextX,nextY
return true
}
else if (arr[nextX,nextY] < value)
{
if (numberSearch(arr, value, minX, maxX, nextY + 1, maxY))
return true
return numberSearch(arr, value, nextX + 1, maxX, minY, nextY)
}
else
{
if (numberSearch(arr, value, minX, nextX - 1, minY, maxY))
return true
reutrn numberSearch(arr, value, nextX, maxX, minY, nextY)
}
“ZigZag方法”和O(log N)二元搜索方法。我以为我会做一些测试，比较两种方法和一些不同的设置。以下是详细信息：
在每次测试中，阵列都是N x N平方，N从125到8000不等（我的JVM堆最大可以处理）。对于每个数组大小，我在数组中选择一个随机位置来放置一个O(N+M)。然后我随处可能放置一个2（在2的右侧和下方），然后用3填充阵列的其余部分。一些早期的评论者似乎认为这种类型的设置会产生两种算法的最坏情况运行时间。对于每个阵列大小，我为2（搜索目标）选择了100个不同的随机位置并运行测试。我记录了每种算法的平均运行时间和最差情况运行时间。因为它发生得太快而无法在Java中获得良好的ms读数，并且因为我不相信Java的nanoTime（），所以我重复每次测试1000次，只是为了一直添加一个统一的偏差因子。结果如下：
ZigZag在平均和最差情况下的每次测试中都击败了二进制，但是，它们或多或少都在一个数量级之内。
这是Java代码：
1这是问题下限的简短证明。
你不能比线性时间做得更好（就数组维度而言，不是元素数量）。在下面的数组中，标记为public class SearchSortedArray2D {
static boolean findZigZag(int[][] a, int t) {
int i = 0;
int j = a.length - 1;
while (i <= a.length - 1 && j >= 0) {
if (a[i][j] == t) return true;
else if (a[i][j] < t) i++;
else j--;
}
return false;
}
static boolean findBinarySearch(int[][] a, int t) {
return findBinarySearch(a, t, 0, 0, a.length - 1, a.length - 1);
}
static boolean findBinarySearch(int[][] a, int t,
int r1, int c1, int r2, int c2) {
if (r1 > r2 || c1 > c2) return false;
if (r1 == r2 && c1 == c2 && a[r1][c1] != t) return false;
if (a[r1][c1] > t) return false;
if (a[r2][c2] < t) return false;
int rm = (r1 + r2) / 2;
int cm = (c1 + c2) / 2;
if (a[rm][cm] == t) return true;
else if (a[rm][cm] > t) {
boolean b1 = findBinarySearch(a, t, r1, c1, r2, cm - 1);
boolean b2 = findBinarySearch(a, t, r1, cm, rm - 1, c2);
return (b1 || b2);
} else {
boolean b1 = findBinarySearch(a, t, r1, cm + 1, rm, c2);
boolean b2 = findBinarySearch(a, t, rm + 1, c1, r2, c2);
return (b1 || b2);
}
}
static void randomizeArray(int[][] a, int N) {
int ri = (int) (Math.random() * N);
int rj = (int) (Math.random() * N);
a[ri][rj] = 2;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == ri && j == rj) continue;
else if (i > ri || j > rj) a[i][j] = 3;
else a[i][j] = 1;
}
}
}
public static void main(String[] args) {
int N = 8000;
int[][] a = new int[N][N];
int randoms = 100;
int repeats = 1000;
long start, end, duration;
long zigMin = Integer.MAX_VALUE, zigMax = Integer.MIN_VALUE;
long binMin = Integer.MAX_VALUE, binMax = Integer.MIN_VALUE;
long zigSum = 0, zigAvg;
long binSum = 0, binAvg;
for (int k = 0; k < randoms; k++) {
randomizeArray(a, N);
start = System.currentTimeMillis();
for (int i = 0; i < repeats; i++) findZigZag(a, 2);
end = System.currentTimeMillis();
duration = end - start;
zigSum += duration;
zigMin = Math.min(zigMin, duration);
zigMax = Math.max(zigMax, duration);
start = System.currentTimeMillis();
for (int i = 0; i < repeats; i++) findBinarySearch(a, 2);
end = System.currentTimeMillis();
duration = end - start;
binSum += duration;
binMin = Math.min(binMin, duration);
binMax = Math.max(binMax, duration);
}
zigAvg = zigSum / randoms;
binAvg = binSum / randoms;
System.out.println(findZigZag(a, 2) ?
"Found via zigzag method. " : "ERROR. ");
//System.out.println("min search time: " + zigMin + "ms");
System.out.println("max search time: " + zigMax + "ms");
System.out.println("avg search time: " + zigAvg + "ms");
System.out.println();
System.out.println(findBinarySearch(a, 2) ?
"Found via binary search method. " : "ERROR. ");
//System.out.println("min search time: " + binMin + "ms");
System.out.println("max search time: " + binMax + "ms");
System.out.println("avg search time: " + binAvg + "ms");
}
}
的每个元素可以是5或6（独立于其他元素）。因此，如果您的目标值是6（或5），则算法需要检查所有这些值。
*当然，这也扩展到更大的阵列。这意味着1 2 3 4 *
2 3 4 * 7
3 4 * 7 8
4 * 7 8 9
* 7 8 9 10
是最佳的。
更新：正如Jeffrey L Whitledge所指出的那样，它只是最优的运行时间与输入数据大小的渐近下限（作为单个变量处理）。可以改善在两个阵列维度上被视为双变量函数的运行时间。
我认为这是答案，它适用于任何类型的排序矩阵
this answer
有趣的问题。考虑这个想法 - 创建一个边界，其中所有数字都大于您的目标，另一个边界所有数字都小于您的目标。如果在两者之间留下任何东西，那就是你的目标。
如果我在你的例子中寻找3，我会读到第一行，直到我达到4，然后寻找大于3的最小相邻数字（包括对角线）：
1 2 4 5 6 2 3 5 7 8 4 6 8 9 10 5 8 9 10 11
现在我对那些小于3的数字做同样的事情：
1 2 4 5 6 2 3 5 7 8 4 6 8 9 10 5 8 9 10 11
现在我问，这两个界限内是什么？如果是的话，它必须是3.如果不是，则没有3.间接的排序，因为我实际上没有找到该数字，我只是推断它必须在那里。这还有计算所有3的额外奖励。
我在一些例子上尝试了这个，它似乎工作正常。
通过阵列对角线进行二进制搜索是最佳选择。我们可以找出该元素是否小于或等于对角线中的元素。
A.对目标号码所在的那些行进行二进制搜索。
B.使其成为图形：通过始终使用最小的未访问的邻居节点来查找数字，并在找到太大的数字时进行回溯