二维数组中的二进制搜索

我想知道，可以二分查找应用于一个二维数组？二维数组中的二进制搜索

条件上的数组是什么？排序在2D？
会是什么时候复杂度它？
算法如何改变搜索的边界（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);

谢谢

来源

2010-12-12 Betamoo

有什么特别的你想要实现？ – NPE 2010-12-13 14:53:24

我的第一个建议是让你的一维算法得到解决。可能有几个界限问题。考虑一个大小为1的数组。这里'min = 1'和'max = 1'。然后'mid：= min +（max-min）div 2'产生'mid = 0'（假设整数运算）。然后谁知道'A [mid]'等于什么（给定'A'被索引为：1..N）。 – NealB 2010-12-13 16:23:26

@NealB这只是维基百科中的代码...它并不重要，它只是为了演示.. – Betamoo 2010-12-14 12:45:41

二进制搜索要求您的数组排序。反过来，排序需要数组元素上的总体排序关系。在1-D中很容易理解这意味着什么。我认为你必须在你的二维数组中定义一维索引，并确保数组元素是沿着该索引排序的。

您有多种一维索引方案可供选择，基本上可以使用任何空间填充曲线。想到的最明显的是：

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

赞@Bart Kiers，我不明白你的第二点。

来源

2010-12-12 12:13:40

请看看修改后的问题.. – Betamoo 2010-12-12 13:22:57

我看着修改后的问题。现在我不明白的是第三不是第二。 – 2010-12-12 14:53:36

我想过这个问题，去年...所以，我会选用这种方法：

考虑你的二维数组表示在平面上的点。例如，你的元素A [i] [j]表示一个x = i和y = j的点。在飞机上使用二进制搜索我有点所有使用这个情况分：

点P1 < P2当且仅当：

（x坐标P1）的<（P2的x坐标）
（x坐标p1的）=（P2的x坐标）和（P1的y坐标）<（p2的Y坐标）

Othwerwise P1> P2 =。

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

换句话说：

A [i] [j]> A [k]的[j]的当且仅当（ⅰ> K）。（在不同的行和列中）
A [i] [j]> A [i] [k]当且仅当（j> k）。（在同一行和不同列中）

考虑你的数组有N行和M列。

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

现在你有一维数组： - 现在，你应该（即暂时）使用此公式（临时阵列T）将您的二维数组一维数组。以通常的方式分类。现在您可以使用简单的二进制搜索算法进行搜索。

或者您可以使用此公式将您的排序阵列回二维数组：

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名称），当你发现你的牙齿列，你可以调用此行中的另一个二分搜索（A [mid]中的二分搜索）。

复杂度的两种方法：

用于trasformed阵列简单二进制搜索：用于2D阵列的两个二进制搜索日志（N * M）
：日志（N）为外搜索（按行） + log（M）用于内部搜索（按列）。

使用对数函数的性质，我们可以简化最后一个表达式：日志（N）+日志（M）=日志（N * M）。

所以，我们证明，这两种方法具有相同的复杂性，并不重要，哪一个使用。但是，如果对你不难，我建议你简单地将你的数组转换为1-D，并使用简单的二进制搜索（它非常简单，易于调试和检查）。

来源

2010-12-12 14:25:32 Ilnur

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

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

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方法降低了时间复杂度。

来源

2015-08-25 10:03:07

您可以将二维数组转换为一维数组并在此处执行二分查找。 mxn阵列的复杂度为O(log(m * n))。

来源

2017-03-30 00:22:23

二维数组中的二进制搜索

回答

相关问题