二维数组中的二分查找

Question

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

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

编辑：

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

普通二进制 searchrh 的伪代码：

 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

我去年考虑过这个问题......所以，我选择了这种方法：

考虑你的二维数组代表平面上的点。例如，元素 A[i][j] 表示 x = i 且 y = j 的点。为了在平面上使用二分搜索，我使用以下条件对所有点进行排序：

点 p1 < p2 当且仅当：

• (p1 的 x 坐标) < (p2的x坐标)
• (p1的x坐标)＝(p2的x坐标)并且(p1的y坐标)＜0。 (p2的y坐标)

否则p1>=p2。

现在，如果我们查看二维数组，第二行中的元素应该大于第一行中的元素。在同一行中的元素照常排序（根据其列号）。

换句话说：

• A[i][j]＞ A[k][j]当且仅当(i>k)。 (不同行、同一列)
• A[i][j]> A[i][k]当且仅当(j＞k)。 （在同一行和不同列）

假设你的数组有 N 行和 M 列。现在您应该（暂时）使用以下公式将 2D 数组转换为 1D 数组（T - 临时数组）：

for i:=0 to N-1 do
    for j:=0 to M-1 do
        T[i*N + j]:= A[i][j];

现在您拥有 1D 数组。按照通常的方式排序。现在您可以使用简单的二分搜索算法在其中进行搜索。

或者，您可以使用以下公式将排序后的数组转换回二维数组：

for i:=0 to N*M-1 do
    A[i div N][i - (i div N)*N]:= T[i];

并使用两种二分搜索：

一种按 x 坐标（按我们的意思是行）搜索，另一种按 y 坐标（按我们的意思按列）搜索元素在同一行。

换句话说，当您计算 mid = mid + (max - min) div 2 时，您可以将元素 A[mid][0] 与您的关键元素进行比较（在您的代码中它有 x name），当您找到包含您的元素的行时，您可以在该行中调用另一个二分搜索（A[mid]中的二分搜索）。

两种方法的复杂性：

• 对于转换数组中的简单二分搜索：log(N*M)
• 对于二维数组中的两次二分搜索：log(N) 对于外部搜索（在rows) + log(M) 用于内部搜索（以列为单位）。

利用对数函数的性质，我们可以简化最后一个表达式：log(N) + log(M) = log(N*M)。

因此，我们证明，这两种方法具有相同的复杂性，并且使用哪一种并不重要。

但是，如果这对您来说不难，我建议您只需将数组转换为一维数组并使用简单的二分搜索（它非常简单且易于调试和检查）。

Answer 3

二分查找以分而治之的方式工作，

int r = arr.length; // ROW Count
int c = arr[0].length; // Column Count
int start = 0; // Initialize with the 0
int end = r*c-1; // Last Index

我们将不断迭代 while 循环，每次根据要求更新开始和结束索引..
while(start <= end){

int mid = (start+end)/2;
int midX = mid/c;
int midY = mid%c;

如果当前值等于搜索元素，那么我们只需打印并返回它。

if(arr[midX][midY] == searchElement){
return true;
}

如果当前值小于搜索元素，则我们只需将中间值更新为 mid = mid + 1

if(arr[midX][midY] < searchElement){
start = mid+1;
}

如果当前值大于搜索元素，则只需将中间值更新为 mid = mid - 1

else{
end = mid-1;
}

Answer 4

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

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

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

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

Answer 5

假设它是一个一维数组，并在分而治之时计算正确的行和列：

/**
* @param grid {[[number]]} A 2D NxM grid of numbers
* @param targetValue {number} The target value to search
* @return {[number]} A list containing the row and column. For example, [0,5] means row 0 column 5 
*/
function search (grid, targetValue) {
    let rows = grid.length;
    let cols = grid[0].length;

    let leftBound = 0;
    let rightBound = rows * cols - 1;

    while (true) {
        let currentIndex = parseInt((leftBound + rightBound) / 2);
        let currentRow = parseInt(currentIndex / cols);
        let currentColumn = currentIndex % cols;
        let currentValue = grid[currentRow][currentColumn];

        if (currentValue === targetValue) {
            return [currentRow, currentColumn];
        }
        else if (rightBound <= leftBound) {
            return [-1, -1];
        }
        else if (currentValue < targetValue) {
            leftBound = currentIndex + 1;
        }
        else {
            rightBound = currentIndex - 1;
        }
    }

}

search([[11,12,15,23],[25,28,31,32],[35,45,47,47],[50,51,55,56],[65,65,78,88]], 45);

Answer 6

不，不可能对二维数组应用二分搜索。

二分查找的要求：

要求 1：项目已排序

在一维数组中，这意味着什么。
但这对于二维数组到底意味着什么呢？

要求 2：2 个方向

二分查找要求当您选择其中的一项时，您可以从那里进入 2 个方向。

由于排序，每当您选择一个项目时，该项目都会提供足够的信息来了解您需要在两个方向中的哪一个方向继续搜索。这允许将搜索范围分为两部分，这就是我们称之为二进制的原因。

如果您在 2D 数组中选择一个项目，则有 4 个可能的方向（甚至更多：您也可以沿对角线移动）。即使所有项目都以某种方式排序，一项中的信息也无法告诉您必须朝哪个方向以及如何根据该方向拆分数组。

仅当您可以将二维数组转换为已排序的一维数组时，才可以进行二分查找。
如果可以定义一个函数，将索引 x 和 y 组合成包含 2D 数组中所有项目的已排序虚拟一维数组的索引 i，并且可以从 i 计算回 x 和 y，那么您可以对其使用二分搜索虚拟一维阵列。该函数取决于二维数组中的项目如何排序。但这意味着您正在一维数组而不是二维数组上进行二分搜索！

Answer 7

这是二分搜索解决方案，适用于所有测试用例。

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int h = 0, w = matrix[0].size(), x;
    while(h < matrix.size() && w && (x = matrix[h][w-1]) != target) {
        if (x > target) w--;
        else h++;
    }
    return x == target;
}

Answer 8

class Solution {
  public boolean searchMatrix(int[][] matrix, int target) {
    int n = matrix.length;
    int m = matrix[0].length;
    int low =0, high=n*m-1;

    while(low <= high) {
      int mid =(low+high)/2;
      int row = mid/m;
      int col = mid%m;

      if (matrix[row][col] == target) return true;
      else if (matrix[row][col] < target) low = mid+1;
      else high = mid-1;
    }
    return false;
  }
}

Answer 9

您可以将二维数组转换为一维数组并在此处进行二分搜索。对于 mxn 数组，复杂度为 O(log(m * n))。