如何从左到右,从上到下排序的二维数组中搜索数字？

Question

我最近接受了这个面试问题,我很好奇它是一个很好的解决方案.

假设我有一个二维数组,其中数组中的所有数字从左到右,从上到下依次递增.

搜索和确定目标号码是否在阵列中的最佳方法是什么？

现在,我的第一个倾向是利用二进制搜索,因为我的数据已经排序.我可以确定O(log N)时间内的数字是否在一行中.然而,正是这两个方向让我失望.

我认为可能有用的另一种解决方案是从中间的某个地方开始.如果中间值小于我的目标,那么我可以确定它在中间的矩阵的左方形部分.然后我沿着对角线移动并再次检查,减小了目标可能存在的方格的大小,直到我对目标数字进行了磨练.

有没有人有解决这个问题的好主意？

示例数组:

从左到右,从上到下排序.

1  2  4  5  6  
2  3  5  7  8  
4  6  8  9  10  
5  8  9  10 11  

Answer 1

这是一个简单的方法:

1. 从左下角开始.
2. 如果目标小于该值,则必须高于我们,因此向上移动一个.
3. 否则我们知道目标不能在该列中,所以向右移动一个.
4. 转到2.

对于一个NxM数组,这运行O(N+M).我认为要做得更好很难.:)

编辑:很多很好的讨论.我在谈论上面的一般情况; 显然,N无论M 是否小,您都可以使用二分搜索方法在接近对数时间的情况下执行此操作.

以下是一些细节,对于那些好奇的人:

历史

这种简单的算法称为鞍背搜索.它已经存在了一段时间,它是最佳的N == M.一些参考:

• David Gries,编程学.Springer-Verlag,1989.
• Edsgar Dijkstra,The Saddleback Search.注EWD-934,1985.

然而,当N < M直觉表明二进制搜索应该能够做得比O(N+M)以下更好:例如,当N == 1纯二进制搜索将以对数而不是线性时间运行时.

最坏情况

理查德·伯德(Richard Bird)研究了这种直觉,二元搜索可以在2006年的论文中改进Saddleback算法:

• 理查德·伯德S.,提高马鞍搜索:在算法设计的教训,在项目建设的数学,第82--89,成交量4014,2006.

使用一种相当不寻常的会话技术,Bird告诉我们,因为N <= M这个问题有一个较低的界限?(N * log(M/N)).这个界限是有意义的,因为它给我们时的线性性能N == M和对数性能时N == 1.

矩形阵列的算法

一种使用逐行二进制搜索的方法如下所示:

1. 从一个矩形阵列开始N < M.我们说的N是行和M列.
2. 在中间行进行二进制搜索value.如果我们找到它,我们就完成了.
3. 否则我们找到了一对相邻的数字,s并g在哪里s < value < g.
4. 上方和左侧的数字矩形s小于value,因此我们可以消除它.
5. 下方和右侧的矩形g大于value,因此我们可以消除它.
6. 对于剩余的两个矩形中的每一个,转到步骤(2).

就最坏情况复杂性而言,该算法确实log(M)可以消除一半可能的解决方案,然后在两个较小的问题上递归调用两次.我们必须log(M)为每一行重复该工作的较小版本,但如果行数与列数相比较小,那么能够以对数时间消除所有这些列开始变得值得.

这给了算法一个复杂性T(N,M) = log(M) + 2 * T(M/2, N/2),Bird表明了这一点O(N * log(M/N)).

Craig Gidney发布的另一种方法描述了一种类似于上述方法的算法:它使用步长检查一次一行M/N.他的分析表明,这O(N * log(M/N))也会带来性能.

绩效比较

Big-O分析一切都很好,但这些方法在实践中的效果如何？下面的图表检查了越来越"方形"数组的四种算法:

("天真"算法只搜索数组的每个元素.上面描述了"递归"算法."混合"算法是Gidney算法的一种实现.对于每个数组大小,通过在固定集上对每个算法进行计时来测量性能1,000,000个随机生成的数组.)

一些值得注意的要点:

• 正如所料,"二分搜索"算法在矩形阵列上提供了最佳性能,而Saddleback算法在方阵上工作得最好.
• Saddleback算法比1-d阵列的"天真"算法表现更差,可能是因为它对每个项目进行了多次比较.
• "二分搜索"算法在方阵上采用的性能可能是由于运行重复二进制搜索的开销.

摘要

巧妙地使用二进制搜索可以为O(N * log(M/N)矩形和方形阵列提供性能.在O(N + M)"马鞍"的算法简单得多,但是从性能下降遭受的阵列变得越来越矩形.

Answer 2

这个问题需要?(b lg(t))时间,在哪里b = min(w,h)和t=b/max(w,h).我在这篇博文中讨论了解决方案.

下限

攻击者可以?(b lg(t))通过将自身限制为主对角线来强制算法进行查询:

图例:白色单元格较小,灰色单元格较大,黄色单元格较小或相等,橙色单元格较大或相等.攻击者强制解决方案是算法查询的最后一个黄色或橙色单元格.

请注意,有b独立的大小排序列表t,要求?(b lg(t))查询完全消除.

算法

1. (假设不失一般性w >= h)
2. 将目标项目与t有效区域右上角左侧的单元格进行 比较
   • 如果单元格的项目匹配,则返回当前位置.
   • 如果单元格的项目小于目标项目,t则使用二进制搜索消除行中的剩余单元格.如果在执行此操作时找到匹配项,请返回其位置.
   • 否则,单元格的项目不仅仅是目标项目,从而消除了t短列.
3. 如果没有剩余有效区域,则返回失败
4. 转到第2步

寻找物品:

确定项目不存在:

图例:白色单元格较小,灰色单元格较大,绿色单元格相同.

分析

有b*t短列可以消除.有很b长的行要消除.消除长排成本的O(lg(t))时间.消除t短列需要花费O(1)时间.

在最坏的情况下,我们必须消除每一列和每一行,花费时间O(lg(t)*b + b*t*1/t) = O(b lg(t)).

请注意,我假设lg钳位到1以上的结果(即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;
}

Answer 3

我会对这个问题使用分而治之的策略,类似于你的建议,但细节有点不同.

这将是对矩阵子范围的递归搜索.

在每个步骤中,选择范围中间的元素.如果找到的值是您正在寻找的,那么您就完成了.

否则,如果找到的值小于您要搜索的值,则表示它不在您当前位置的上方和左侧的象限中.因此,递归搜索两个子范围:当前位置下方的所有内容(专有),以及当前位置或其上方的所有内容(仅限于).

否则,(找到的值大于您要搜索的值)您知道它不在您当前位置下方和右侧的象限中.因此,递归搜索两个子范围:当前位置左侧的所有内容(排他性),以及当前列上当前位置或右侧列上的所有内容(排他地).

巴德达,你找到了它.

请注意,每个递归调用仅处理当前子范围,而不是(例如)当前位置上方的所有行.只是当前子范围内的那些.

这是你的一些伪代码:

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)
}

Answer 4

到目前为止,两个主要答案似乎是O(log N)"ZigZag方法"和O(N+M)二元搜索方法.我以为我会做一些测试,比较两种方法和一些不同的设置.以下是详细信息:

在每次测试中,阵列都是N x N平方,N从125到8000不等(我的JVM堆最大可以处理).对于每个数组大小,我在数组中选择一个随机位置来放置一个2.然后,我3随处可能(在2的右侧和下方),然后填充阵列的其余部分1.一些早期的评论者似乎认为这种类型的设置会产生两种算法的最坏情况运行时间.对于每个阵列大小,我为2(搜索目标)选择了100个不同的随机位置并运行测试.我记录了每种算法的平均运行时间和最差情况运行时间.因为它发生得太快而无法在Java中获得良好的ms读数,并且因为我不相信Java的nanoTime(),所以我重复每次测试1000次,只是为了一直添加一个统一的偏差因子.结果如下:

ZigZag在平均和最差情况下的每次测试中都击败了二进制,然而,它们或多或少都在一个数量级之内.

这是Java代码:

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");
    }
}

Answer 5

这是问题下限的简短证明.

你不能比线性时间做得更好(就数组维度而言,不是元素数量).在下面的数组中,标记为的每个元素*可以是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所指出的那样,它只是最优的运行时间与输入数据大小的渐近下限(作为单个变量处理).可以改善在两个阵列维度上被视为双变量函数的运行时间.

Answer 6

A. 对目标数字可能所在的行进行二分查找。

B. 使其成为一个图：通过始终采用最小的未访问邻居节点来查找数字，并在发现太大数字时回溯