二维数组中的二进制搜索 [英] Binary Search in 2D Array

问题描述

我想知道，可以在 2D阵列上应用 binary search 吗?

I wonder, can binary search be applied on a 2D array?

• 阵列上的条件是什么?在2D上排序??
• 复杂度是几点?
• 算法将如何更改搜索的边界(minX，maxX，minY，maxY)?

• What would the conditions on the array be? Sorted on 2D??
• What would be the time complexity for it?
• How would the algorithm change the boundary of the search (minX,maxX,minY,maxY) ??

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

Binary Search on 1D maintains 2 pointers minX and maxX.. It selects the middle index (minX+maxX)/2 and compare it with the search value, if greater then change maxX, else change minX... until minX>=maxX

正常二进制seacrh的伪代码:

Pseudo code for normal binary 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);

谢谢

推荐答案

我以简单的方式在 O(m + n)时间复杂度()中解决了该问题，其中m =否.行数，n =否.列.

I solved it in a simple way in O(m + n) time complexity, where m = no. of rows and n = no. of columns.

算法很简单::我从右上角开始(我们也可以从左下角开始)，如果当前元素，则向左移动大于要搜索的值，如果当前元素，则大于底部小于要搜索的值.

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代码类似于:

The java code is like:

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

}

您可以使用称为 改进的二进制分区 .

You can further reduce the time complexity by using a method called Improved Binary Partition.

这篇关于二维数组中的二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！