Algorithmic puzzle
Май 12th, 2008 | by OleXaa |

Имеется некая упорядоченная матрица с размером MxN, содержащая числа отсортированные по столбцам и строкам Необходимо предложить наиболее оптимальный вариант поиска элемента в матрице.
Java, JavaScript, C#, PHP, Ruby

Имеется некая упорядоченная матрица с размером MxN, содержащая числа отсортированные по столбцам и строкам Необходимо предложить наиболее оптимальный вариант поиска элемента в матрице.
9 Responses to “Algorithmic puzzle”
By Ni@m on Май 12, 2008 | Reply
Пройтись по главной диагонали, сравнивать, если меньше искомого, значит на второй диагонали, которая пересекает текущую ячейку - вниз или вверх идти - сравнить с ближайшим элементов, нет - переходить к следующей.
By Vadim Voituk on Май 12, 2008 | Reply
Квадратная версия бинарного поиска?
By COTOHA on Май 13, 2008 | Reply
с учётом того, что цифры не уникальны, то что является правильным ответом?
индекс любого элемента с заданным значением или все индексы элементов с заданным значением?
By Olexa on Май 14, 2008 | Reply
индекс любого элемента с заданным значением - слишком просто
интересует алгоритм нахождения всех элементов с заданным значением?
By COTOHA on Май 14, 2008 | Reply
как бы надо или свои вопросы придумывать или указывать источник.
http://www.dev102.com/2008/05/12/a-programming-job-interview-challenge-3/
By COTOHA on Май 14, 2008 | Reply
там авторы вопроса разошлись во мнениях
один говорит, что можно дать первый попавшийся, а второй говорит, что можно считать, что цифры уникальные
By Olexa on Май 14, 2008 | Reply
так, той пазл я взяв саме там(до речі, якщо цікаво, там є ще два завдання). Однак я дозволив собі трошки ускладнити завдання: елементи матриці далеко не унікальні,і хотілось би знайти алгоритм пошуку всіх елементів з заданим значенням. Сам рішення ще не маю. на разі, найкраще, що прийшло в голову- це ділити матрицю на чотири частини(бінарний пошук серед елементів діагоналі… на межі більше-менше.. коли один елемент більший ніж той, що необхідно знайти, а наступний вже менший).. потім частину(містить елементи зі значенням меншим ніж те, що шукається) викидую з пошуку, а решту знову ділю на частини..
але підозрюю, що це далеко не оптимальний варіант
By Григорii on Июнь 6, 2008 | Reply
Хороший блог
Люблю почитывать каждое утро (ну и в другое время тоже :)).
By Алексей on Авг 10, 2008 | Reply
Хорошо написано. Поставил у себя ссылочку