Дана двумерная матрица из n строк и m столбцов. Все строки и столбцы этой матрицы отсортированы по горизонтали и вертикали соответственно. Написать метод, реализующий алгоритм поиска элемента.
bool find_elem(int** matrix, int elem, int n, int m) { //ваш код };
| 1 | Цель задания | быстрая проверка базовых знаний основных алгоритмов и средств их реализации |
| 2 | Время выполнения | 20-30 минут |
| 3 | Формат выполнения | код пишется на листике, без доступа к документации |
Критерии оценки FulcrumWeb:
Кандидат должен продемонстрировать, что понимает ключевое слово задачи “ОТСОРТИРОВАНЫ” и знает, как использовать это обстоятельство для написания максимально эффективного поиска.
Ожидаемые вопросы:
- Известен ли порядок сортировки?
Оценка результатов:
Для начинающего программиста полное отсутствие вопросов простительно. При этом ожидается реализация, основанная на каком-то самостоятельно выбранном порядке сортировки. Приветствуется, если кандидат даст оценку сложности написанного им алгоритма. При этом мы надеемся не увидеть банальной реализации алгоритма линейного поиска.
От программистов с опытом работы мы ожидаем вопроса о порядке сортировки. Приемлема реализация, основанная на каком-то конкретном допущении о порядке сортировке, но при этом желательно продемонстрировать понимание того, какие нужны модификации, если порядок сортировки изменится. Более продвинутым будет общее решение с использованием компараторов.
Решение на 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); }
7 Коммент. : “Поиск элемента”
Бинарный поиск для двумерного массива? Интересно….
Да – интересно. Только поиск все равно сводится к поиску в одномерном массиве…
Как сейчас помню – была такая задача на моем первом собеседовании в 1999-м году – сразу после ВУЗа. привел массив к одномерному и использовал сдвиг для деления на 2 (хоть компилятор сейча достаточно умный и сам заменить int/2 сдвигом – но нужно было “поумничать” для вида))) судя по предложению рботы – приводить к одномерному, наверное, было правильно
Можно одномерный массив не использовать. Пусть матрица имеет размер MxN и отсортировано все как ниже приведено. Начинаем с правого верхнего угла (число 20). Один цикл. В нем смещаемся за одну итерацию либо на шаг влево, либо на шаг вниз…
Через некоторое время я опубликую решение
Хочу загрузить файл с решением. Вот ссылка http://zalil.ru/32899782 Доходит ли он до вас?
Доходит и загружается, но файл содержит всего одну строку текста.
Решение на C++ приведено