矩阵的二进制搜索

Question

Write an efficient algorithm that searches for a value in an m x n matrix.

This matrix has the following properties:

-Integers in each row are sorted from left to right.
-The first integer of each row is greater than or equal to the last integer of the previous row.

Example:

Consider the following matrix:

[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return 1 ( 1 corresponds to true )

Return 0 / 1 ( 0 if the element is not present, 1 if the element is present ) for this problem

我的解决方案在 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;
    }
}

Answer 1

我觉得分享的程序好像有逻辑错误

第一个while循环更新结束值时，如果结束值等于start，则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;
    }
}

Answer 2

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

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! ");
    }
}

这个函数打印要搜索的元素的行和列如果exists.You可以修改这段代码，如果你想让这个函数根据搜索操作return一个值。

Answer 3

您的行搜索循环中存在逻辑错误。我做了一个更正，我还添加了这个算法的边界 conditions.Time 复杂度是 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;
    }
}

Answer 4

好的，您绝不能做的第一件事是，您不能将矩阵物理地连接成一维向量，因为这是 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;
}

Answer 5

既然行和列是排序的，那么按照你说的二分查找就可以了。这是 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

矩阵的二进制搜索

Binary search of a Matrix

algorithm

matrix

binary-search