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

Опубликовано 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);
}

9 Коммент. : “Поиск элемента”

  1. Бинарный поиск для двумерного массива? Интересно….

    • Да – интересно. Только поиск все равно сводится к поиску в одномерном массиве…

      • Как сейчас помню – была такая задача на моем первом собеседовании в 1999-м году – сразу после ВУЗа. привел массив к одномерному и использовал сдвиг для деления на 2 (хоть компилятор сейча достаточно умный и сам заменить int/2 сдвигом – но нужно было “поумничать” для вида))) судя по предложению рботы – приводить к одномерному, наверное, было правильно

        • ovelychkko says:

          Если масив создан так:
          int** matr1 = new int*[n];
          for (int i = 0; i < n; i++) matr1[i] = new int[m];
          то работать с указателем matr1 как с одномерным массивом не получится

      • Можно одномерный массив не использовать. Пусть матрица имеет размер MxN и отсортировано все как ниже приведено. Начинаем с правого верхнего угла (число 20). Один цикл. В нем смещаемся за одну итерацию либо на шаг влево, либо на шаг вниз…

        1	5	15	20
        2	7	21	28
        5	10	25	30
        

        Через некоторое время я опубликую решение

  2. Dmitriy says:

    Хочу загрузить файл с решением. Вот ссылка http://zalil.ru/32899782 Доходит ли он до вас?

  3. Galina says:

    Решение на C++ приведено

  4. #include <iostream>
     
    //бинарный поиск по строкам
    bool find_elem(int** matrix, int elem, int n, int m) {
    	for(int i = 0; i < n; i++) {
    		int mid = (m - 1) / 2;
    		for(int j = 0; j < mid; j++) {
    			if(matrix[i][mid] == elem)
    				return true;
    			if(matrix[i][mid] > elem) { //двигаемся вправо
    				mid -= (m - mid) / 2;
    			} else { //идём влево
    				mid += (m - mid) / 2;
    			}
    		}
    	}
    	return false;
    }
     
    //альтернатива
    bool find_elem_1(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;
    		//если искомый элемент меньше
    		if(elem < matrix[row][col]) {
    			//передвигаемся на один столбец влево
    			col--;
    } else { //если искомый элемент больше
    	//передвигаемся на одну строку вниз
    	row++;
    }
    }
    }
     
    int main(int argc, char const *argv[]) {
    	int **a;
    	int n;
    	int m;
    	int elem;
     
    	std::cin >> n;
    	std::cin >> m;
    	std::cin >> elem;
    	a = new int *[n];
    	for (int i = 0; i < n; i++) {
    		a[i] = new int[m];
    	}
    	for(int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++) {
    			std::cin >> a[i][j];
    		}
    	}
    	std::cout << "output: " << find_elem(a, elem, n, m) << std::endl;
    	return 0;
    }

Оставить комментарий

Ваш адрес email не будет опубликован.


*