Поиск элемента

Опубликовано Sep 30, 2011 в Массивы и строки | 9 коммент.

, , , ,

Поиск элемента

Дана двумерная матрица из n строк и m столбцов. Все строки и столбцы этой матрицы отсортированы по горизонтали и вертикали соответственно. Написать метод, реализующий алгоритм поиска элемента.

bool find_elem(int** matrix, int elem, int n, int m)
{
  //ваш код
};

Критерии оценки

Кандидат должен продемонстрировать, что понимает ключевое слово задачи “ОТСОРТИРОВАНЫ” и знает, как использовать это обстоятельство для написания максимально эффективного поиска.

Ожидаемые вопросы:

  1. Известен ли порядок сортировки?

Оценка результатов:

Для начинающего программиста полное отсутствие вопросов простительно. При этом ожидается реализация, основанная на каком-то самостоятельно выбранном порядке сортировки. Приветствуется, если кандидат даст оценку сложности написанного им алгоритма. При этом мы надеемся не увидеть банальной реализации алгоритма линейного поиска.

От программистов с опытом работы мы ожидаем вопроса о порядке сортировки. Приемлема реализация, основанная на каком-то конкретном допущении о порядке сортировке, но при этом желательно продемонстрировать понимание того, какие нужны модификации, если порядок сортировки изменится. Более продвинутым будет общее решение с использованием компараторов.

Решение на C++

bool find_elem(int** matrix, int elem, int n, int m)
{
  int row = 0;
  int col = m-1;
  while (row < n && col >= 0)
  {
    if (matrix[row][col] == elem)
    {
      return true;
    } else if (matrix[row][col] > elem)
    {
      col--;
    } else
    {
      row++;
    }
  }
  return false;
};
int _tmain(int argc, _TCHAR* argv[])
{
  int n = 3;
  int m = 4;
  int** matr1 = new int*[n];
  for (int i = 0; i < n; i++) matr1[i] = new int[m];
 
  matr1[0][0] = 1;  matr1[0][1] = 5;  matr1[0][2] = 15;  matr1[0][3] = 20;
  matr1[1][0] = 2;  matr1[1][1] = 7;  matr1[1][2] = 21;  matr1[1][3] = 28;
  matr1[2][0] = 5;  matr1[2][1] = 10;  matr1[2][2] = 25;  matr1[2][3] = 30;
 
  bool  isFound = find_elem(matr1, 21, 3, 4);
        isFound = find_elem(matr1, 11, 3, 4);
}

Решение на C#

 
  static bool find_elem(int[,] matrix, int elem)
    {
 
      int n = matrix.GetLength(0);
      int m = matrix.GetLength(1);
 
      int row = 0;
      int col = m - 1;
      while (row < n && col >= 0)
      {
        if (matrix[row, col] == elem)
        {
          return true;
        }
        else if (matrix[row, col] > elem)
        {
          col--;
        }
        else
        {
          row++;
        }
      }
      return false;
    }
 
static void Main(string[] args)
    {
 
      int n = 3;
      int m = 4;
      int[,] matrix = new int[n, m];
 
      matrix[0, 0] = 1; matrix[0, 1] = 5; matrix[0, 2] = 15; matrix[0, 3] = 20;
      matrix[1, 0] = 2; matrix[1, 1] = 7; matrix[1, 2] = 21; matrix[1, 3] = 28;
      matrix[2, 0] = 5; matrix[2, 1] = 10; matrix[2, 2] = 25; matrix[2, 3] = 30;
 
      bool isFound = find_elem(matrix, 21);
      isFound = find_elem(matrix, 11);
}