矩阵的二分查找

Question

编写一个高效的算法，在 m x n 矩阵中搜索一个值。

该矩阵具有以下特征：

- 每行中的整数从左到右按升序排列。 - 每行的第一个整数大于或等于前一行的最后一个整数。

例如，考虑以下矩阵：

[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]

给定 target = 3，返回 1（即为真）。

对于这个问题，如果元素存在返回 0 / 1（0 表示不存在，1 表示存在）。

我的解决方案在 NetBeans 上运行正常，但在网站上失败。任何帮助将不胜感激。https://www.interviewbit.com/problems/matrix-search/

public class Solution {

    public int searchMatrix(ArrayList<ArrayList<Integer>> a, int b) {
        int r = a.size();
        int c = a.get(0).size();

        int start = 0;
        int end = r - 1;
        // default value is last row for edge case
        int biRow = r -1; // row to search column

        //binary search 1st value of rows
        while (start <= end) {
            int mid = (start + end) / 2;
            if (b == a.get(mid).get(0)) {
                return 1;
            }

            if (a.get(mid).get(0) < b && b < a.get(end).get(0)) {
                if (mid + 1 >= end) {
                    biRow = mid;
                    break;
                }
            } if (b < a.get(mid).get(0)) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        //binary search column of biRow
        start = 0;
        end = c-1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (b == a.get(biRow).get(mid)) {
                return 1;
            }
            if (b < a.get(biRow).get(mid)) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return 0;
    }
}

- Duy Đặng

---

只需将NxM矩阵视为N*M项的数组，具有明显的顺序，并在该坐标变换上应用普通二进制搜索。 - amalloy

Answer 1

好的，首先你绝不能将矩阵物理连接成一个一维向量，因为这样的时间复杂度是O(N*M)，是线性的，不符合我们的要求。

// Easy but TLE code
int Solution::searchMatrix(vector<vector<int> > &A, int B) {
    vector<int> v;
    for(auto a : A) v.insert(v.end(), a.begin(), a.end());
    return binary_search(v.begin(), v.end(), B);
}

因此，关键在于您必须直接在矩阵上进行二分查找，这与直接二分查找非常相似（除了现在您必须自己编写二分查找）。由于您并没有真正访问所有元素，因此时间复杂度为 O（lg（N*M））。

// Less Easy but AC code
int Solution::searchMatrix(vector<vector<int> > &A, int B) {
    int m = A.size(), n = A[0].size(), lo = 0, hi = m*n-1, mi, row, col;
    while(lo <= hi){
        mi = lo + ((hi-lo) >> 1);
        row = mi / n;
        col = mi % n;
        if(A[row][col] == B) return 1;
        else if(A[row][col] > B) hi = mi - 1;
        else lo = mi + 1;
    }
    return 0;
}

- shole

Answer 2

我认为共享程序似乎存在逻辑错误。

当在第一个while循环中更新结束值时，如果结束值等于开始值，则无法更新biRow。

当我像下面这样更新代码时，它运行得很好。

public class Solution {
    public int searchMatrix(ArrayList<ArrayList<Integer>> a, int b) {
        int r = a.size();
        int c = a.get(0).size();
        int start = 0;
        int end = r - 1;
        // default value is last row for edge case
        int biRow = r -1; // row to search column

        //binary search 1st value of rows
        int mid = 0;
        while (start <= end) {
            mid = (start + end) / 2;
            if ( b >= a.get(mid).get(0) && b <= a.get(mid).get(c-1)) {
                break;
            }
            if (b < a.get(mid).get(0)) {
                end = mid-1;
            } else {
                start = mid+1;
            }
       }

        biRow = mid;

        //binary search column of biRow
        start = 0;
        end = c-1;
        while (start <= end) {
            mid = (start + end) / 2;
            if (b == a.get(biRow).get(mid)) {
                return 1;
            }
            if (b < a.get(biRow).get(mid)) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return 0;
    }
}

- Ray

Answer 3

你的行搜索循环中存在逻辑错误。我进行了更正，并添加了边界条件。该算法的时间复杂度为O(logN)。

public class Solution {
    public int searchMatrix(ArrayList<ArrayList<Integer>> a, int b) {
        int r = a.size();
        int c = a.get(0).size();

        // return 0 if b is less than 1st element or greater than last element
        if (b < a.get(0).get(0) || b > a.get(r - 1).get(c - 1))
            return 0;
        int start = 0;
        int end = r - 1;
        // default value is last row for edge case
        int biRow = r - 1; // row to search column

        // binary search 1st value of rows
        while (start <= end) {
            int mid = (start + end) / 2;
            if (b == a.get(mid).get(0)) {
                return 1;
            }

            if (b >= a.get(mid).get(0) && b <= a.get(mid).get(c - 1)) {
                {
                    biRow = mid;
                    break;
                }
            }
            if (b < a.get(mid).get(0)) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        // binary search column of biRow
        start = 0;
        end = c - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (b == a.get(biRow).get(mid)) {
                return 1;
            }
            if (b < a.get(biRow).get(mid)) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return 0;
    }
}

- Suresh A

Answer 4

由于行和列已经排序，正如您所说，二分查找是合适的。这是 Ruby 中一个矩阵上的二分查找实现：

def binary_search_on_matrix(matrix,target)
  row_size = matrix.size
  column_size = matrix[0].size
  left_index = 0
  right_index = (row_size * column_size) - 1  
  while (left_index <= right_index)  
    mid_point = left_index + ((right_index - left_index) / 2)
    row = mid_point / column_size
    col = mid_point % column_size
    value = matrix[row][col] 
    if (value == target)
      return true
    elsif (value > target)
      right_index = mid_point - 1
    else
      left_index = mid_point + 1
    end
 end
  return false
end

- Enow B. Mbi

Answer 5

您可以先将二维数组转换为一维数组，然后执行二分查找操作。您可以参考下面给出的代码：

void search(int a[][10],int search,int m,int n)
{
    int arr[100],i=0,j=0,k=-1;
    for(i=0;i<m;i++)
    for(j=0;j<n;j++)
        arr[++k] = a[i][j];

    int first = 0 , last = k-1 , middle = (first+last)/2;

    while (first <= last)
    {
        if(arr[middle] < search)
        {
            first = middle + 1;

        }
        else if(arr[middle] == search)
        {
            printf("\n Element found at position:( %d , %d")",(middle/n)+1,(middle%n)+1);
            printf(" \n Row : %d",(middle/n)+1);
            printf("\n column : %d",(middle%n)+1);
            break;
        }
        else
        {
             last = middle - 1;
        }
        middle = (first + last)/2;
    }
    if(first > last)
    {
        printf("\n Element not found! ");
    }
}

如果存在要搜索的元素，此函数将打印行和列。如果您希望该函数根据搜索操作返回值，则可以修改此代码。

- Newbieforever

---

将二维数组转换为一维数组的复杂度如何？ - Suresh A

这段代码至少存在两个主要问题。首先，你怎么能确定所有内容都适合大小为100的数组？其次，完全没有必要复制整个矩阵。 - Miljen Mikic