二维数组中的二分搜索

Question

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

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

编辑：

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

普通二进制搜索的伪代码：

 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 = 否。列。

算法很简单：我从右上角开始（我们也可以从左下角开始），如果当前元素大于要搜索的值，则向左移动，如果当前元素小于要搜索的值，则向左移动。

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

您可以使用称为改进二进制分区的方法进一步降低时间复杂度。

Answer 2

二分查找要求对数组进行排序。反过来，排序需要数组元素上的全序关系。在一维中，很容易理解这意味着什么。我认为您必须在二维数组中定义一个一维索引，并确保数组元素沿该索引排序。

您有多种一维索引方案可供选择，基本上任何空间填充曲线都可以。我想到的显而易见的是：

• 从第一个元素开始，沿着每一行阅读，在每行末尾转到下一行的第一个元素。
• 同样，逐列替换。
• 对角化，您依次读取每个对角线。

就像@Bart Kiers一样，我不明白你的第二点。