algorithm - 二维数组中的二进制搜索

Question

我想知道，二进制搜索可以应用于二维数组吗？

• 数组的条件是什么？按二维排序??
• 它的复杂度时间是多少？
• 算法将如何改变搜索边界 (minX,maxX,minY,maxY) ??

编辑:

一维二进制搜索维护 2 个指针 minX 和 maxX.. 它选择中间索引 (minX+maxX)/2 并将其与搜索值进行比较，如果大于则更改 maxX，否则更改 minX ...直到 minX>=maxX

普通二进制seacrh的伪代码:

 min := 1;
  max := N; {array size: var A : array [1..N] of integer}
  repeat
    mid := min + (max - min) div 2;
    if x > A[mid] then
      min := mid + 1
    else 
      max := mid - 1;
  until (A[mid] = x) or (min > max);

谢谢

Answer 1

我以 O(m + n) 时间复杂度的简单方式解决了它，其中 m = no。行和 n = 没有。列数。

The algorithm is simple: I started from top right corner (we can also start from bottom left corner) and move left if current element is greater than the value to be searched and bottom if current element is smaller than the value to be searched.

java代码是这样的:

public static int[] linearSearch(int[][] a, int value) {
    int i = 0, j = a[0].length - 1; // start from top right corner

    while (i < a.length && j >= 0) {
        if (a[i][j] == value) {
            return new int[]{i, j};
        } else if (a[i][j] > value) {
            j--; // move left
        } else {
            i++; // move down
        }
    }
    // element not found
    return new int[]{-1, -1};

}

Gist

您可以使用称为 Improved Binary Partition 的方法进一步降低时间复杂度.