Поиск элемента в упорядоченной матрице

В матрице строки и столбцы отсортированы по возрастанию. Нужно найти позиции некоторого элемента, в примере это 100.

\( \begin{matrix} 60 & 64 & 66 & 67 & 71 & 75 & 76 & 77 & 81 & 85 \\ 62 & 70 & 72 & 73 & 77 & 81 & 85 & 89 & 90 & 93 \\ 63 & 71 & 73 & 75 & 79 & 82 & 88 & 93 & 96 & 97 \\ 63 & 81 & 83 & 84 & 86 & 89 & 92 & 96 & 98 & \bf{100} \\ 72 & 84 & 85 & 87 & 89 & 90 & 94 & 97 & 102 & 106 \\ 78 & 85 & 86 & 91 & 94 & 97 & \bf{100} & 101 & 103 & 110 \\ 87 & 90 & 94 & 96 & \bf{100} & 101 & 104 & 108 & 111 & 114 \\ 90 & \bf{100} & 101 & 105 & 106 & 110 & 111 & 113 & 116 & 120 \\ 94 & 103 & 106 & 110 & 111 & 114 & 117 & 121 & 122 & 125 \\ 95 & 111 & 115 & 117 & 119 & 122 & 125 & 127 & 128 & 130 \end{matrix} \)

Число 100 находится в позициях: (3, 9), (5, 6), (6, 4) и (7, 1). Как решить такую задачу?

Если выбрать некоторый элемент в середине матрицы, то станет видно, что элементы правее и ниже больше или равны ему. Элементы выше и левее — меньше либо равны. Про остальные элементы нельзя ничего сказать наверняка.

\( \definecolor{Custom1}{RGB}{248,105,107} \definecolor{Custom2}{RGB}{99,190,123} \def\CA#1{\color{Custom1}{#1}} \def\CB#1{\color{Gray}{#1}} \def\CC#1{\color{Gray}{#1}} \def\CD#1{\color{Custom2}{#1}} \begin{matrix} \CA{60} & \CA{64} & \CA{66} & \CA{67} & \CA{71} & \CB{75} & \CB{76} & \CB{77} & \CB{81} & \CB{85} \\ \CA{62} & \CA{70} & \CA{72} & \CA{73} & \CA{77} & \CB{81} & \CB{85} & \CB{89} & \CB{90} & \CB{93} \\ \CA{63} & \CA{71} & \CA{73} & \CA{75} & \CA{79} & \CB{82} & \CB{88} & \CB{93} & \CB{96} & \CB{97} \\ \CA{63} & \CA{81} & \CA{83} & \CA{84} & \CA{86} & \CB{89} & \CB{92} & \CB{96} & \CB{98} & \bf{\CB{100}} \\ \CA{72} & \CA{84} & \CA{85} & \CA{87} & 89 & \CD{90} & \CD{94} & \CD{97} & \CD{102} & \CD{106} \\ \CC{78} & \CC{85} & \CC{86} & \CC{91} & \CD{94} & \CD{97} & \CD{\bf{100}} & \CD{101} & \CD{103} & \CD{110} \\ \CC{87} & \CC{90} & \CC{94} & \CC{96} & \bf{\CD{100}} & \CD{101} & \CD{104} & \CD{108} & \CD{111} & \CD{114} \\ \CC{90} & \CC{\bf{100}} & \CC{101} & \CC{105} & \CD{106} & \CD{110} & \CD{111} & \CD{113} & \CD{116} & \CD{120} \\ \CC{94} & \CC{103} & \CC{106} & \CC{110} & \CD{111} & \CD{114} & \CD{117} & \CD{121} & \CD{122} & \CD{125} \\ \CC{95} & \CC{111} & \CC{115} & \CC{117} & \CD{119} & \CD{122} & \CD{125} & \CD{127} & \CD{128} & \CD{130} \end{matrix} \)

В принципе, решение можно построить на основе алгоритма A* и простой эвристики: всегда рассматривать серые направления, красное направление рассматривать только в том случае, когда хотя бы один соседний с текущим элемент там больше либо равен искомому. А зелёное — когда хотя бы один соседний с текущим элементом меньше либо равен искомому. Но эффективную реализацию такого метода написать сложно.

Если раскрасить меньшие числа красным цветом, средние жёлтым, а большие зелёным, станет видно диагонали. Все элементы, равные 100, расположены примерно на одной такой оси.

\( \definecolor{Custom0_0}{RGB}{248,105,107} \definecolor{Custom0_1}{RGB}{248,120,109} \definecolor{Custom0_2}{RGB}{249,127,111} \definecolor{Custom0_3}{RGB}{249,131,112} \definecolor{Custom0_4}{RGB}{250,147,115} \definecolor{Custom0_5}{RGB}{251,162,118} \definecolor{Custom0_6}{RGB}{251,166,118} \definecolor{Custom0_7}{RGB}{251,170,119} \definecolor{Custom0_8}{RGB}{252,185,122} \definecolor{Custom0_9}{RGB}{253,200,125} \definecolor{Custom1_0}{RGB}{248,112,108} \definecolor{Custom1_1}{RGB}{250,143,114} \definecolor{Custom1_2}{RGB}{250,150,115} \definecolor{Custom1_3}{RGB}{250,154,116} \definecolor{Custom1_4}{RGB}{251,170,119} \definecolor{Custom1_5}{RGB}{252,185,122} \definecolor{Custom1_6}{RGB}{253,200,125} \definecolor{Custom1_7}{RGB}{253,215,128} \definecolor{Custom1_8}{RGB}{254,219,129} \definecolor{Custom1_9}{RGB}{254,231,131} \definecolor{Custom2_0}{RGB}{248,116,109} \definecolor{Custom2_1}{RGB}{250,147,115} \definecolor{Custom2_2}{RGB}{250,154,116} \definecolor{Custom2_3}{RGB}{251,162,118} \definecolor{Custom2_4}{RGB}{251,177,120} \definecolor{Custom2_5}{RGB}{252,189,123} \definecolor{Custom2_6}{RGB}{253,212,127} \definecolor{Custom2_7}{RGB}{254,231,131} \definecolor{Custom2_8}{RGB}{247,233,132} \definecolor{Custom2_9}{RGB}{243,232,132} \definecolor{Custom3_0}{RGB}{248,116,109} \definecolor{Custom3_1}{RGB}{252,185,122} \definecolor{Custom3_2}{RGB}{252,192,123} \definecolor{Custom3_3}{RGB}{252,196,124} \definecolor{Custom3_4}{RGB}{253,204,126} \definecolor{Custom3_5}{RGB}{253,215,128} \definecolor{Custom3_6}{RGB}{254,227,130} \definecolor{Custom3_7}{RGB}{247,233,132} \definecolor{Custom3_8}{RGB}{238,230,131} \definecolor{Custom3_9}{RGB}{229,229,131} \definecolor{Custom4_0}{RGB}{250,150,115} \definecolor{Custom4_1}{RGB}{252,196,124} \definecolor{Custom4_2}{RGB}{253,200,125} \definecolor{Custom4_3}{RGB}{253,208,126} \definecolor{Custom4_4}{RGB}{253,215,128} \definecolor{Custom4_5}{RGB}{254,219,129} \definecolor{Custom4_6}{RGB}{255,235,132} \definecolor{Custom4_7}{RGB}{243,232,132} \definecolor{Custom4_8}{RGB}{221,225,130} \definecolor{Custom4_9}{RGB}{204,221,130} \definecolor{Custom5_0}{RGB}{251,173,120} \definecolor{Custom5_1}{RGB}{253,200,125} \definecolor{Custom5_2}{RGB}{253,204,126} \definecolor{Custom5_3}{RGB}{254,223,129} \definecolor{Custom5_4}{RGB}{255,235,132} \definecolor{Custom5_5}{RGB}{243,232,132} \definecolor{Custom5_6}{RGB}{229,228,131} \definecolor{Custom5_7}{RGB}{225,227,131} \definecolor{Custom5_8}{RGB}{216,224,130} \definecolor{Custom5_9}{RGB}{186,215,128} \definecolor{Custom6_0}{RGB}{243,232,132} \definecolor{Custom6_1}{RGB}{254,219,129} \definecolor{Custom6_2}{RGB}{255,235,132} \definecolor{Custom6_3}{RGB}{247,233,132} \definecolor{Custom6_4}{RGB}{229,229,131} \definecolor{Custom6_5}{RGB}{225,227,131} \definecolor{Custom6_6}{RGB}{212,223,130} \definecolor{Custom6_7}{RGB}{195,218,129} \definecolor{Custom6_8}{RGB}{182,214,128} \definecolor{Custom6_9}{RGB}{168,210,127} \definecolor{Custom7_0}{RGB}{254,219,129} \definecolor{Custom7_1}{RGB}{229,229,131} \definecolor{Custom7_2}{RGB}{225,227,131} \definecolor{Custom7_3}{RGB}{208,222,130} \definecolor{Custom7_4}{RGB}{204,221,130} \definecolor{Custom7_5}{RGB}{186,215,128} \definecolor{Custom7_6}{RGB}{182,214,128} \definecolor{Custom7_7}{RGB}{173,212,128} \definecolor{Custom7_8}{RGB}{160,208,127} \definecolor{Custom7_9}{RGB}{143,203,126} \definecolor{Custom8_0}{RGB}{255,235,132} \definecolor{Custom8_1}{RGB}{216,224,130} \definecolor{Custom8_2}{RGB}{204,221,130} \definecolor{Custom8_3}{RGB}{186,215,128} \definecolor{Custom8_4}{RGB}{182,214,128} \definecolor{Custom8_5}{RGB}{169,210,127} \definecolor{Custom8_6}{RGB}{156,207,127} \definecolor{Custom8_7}{RGB}{138,202,126} \definecolor{Custom8_8}{RGB}{134,201,126} \definecolor{Custom8_9}{RGB}{121,197,125} \definecolor{Custom9_0}{RGB}{251,234,132} \definecolor{Custom9_1}{RGB}{182,214,128} \definecolor{Custom9_2}{RGB}{164,209,127} \definecolor{Custom9_3}{RGB}{156,207,127} \definecolor{Custom9_4}{RGB}{147,204,126} \definecolor{Custom9_5}{RGB}{134,201,126} \definecolor{Custom9_6}{RGB}{121,197,125} \definecolor{Custom9_7}{RGB}{113,194,124} \definecolor{Custom9_8}{RGB}{108,193,124} \definecolor{Custom9_9}{RGB}{99,190,123} \begin{matrix} \color{Custom0_0}{60} & \color{Custom0_1}{64} & \color{Custom0_2}{66} & \color{Custom0_3}{67} & \color{Custom0_4}{71} & \color{Custom0_5}{75} & \color{Custom0_6}{76} & \color{Custom0_7}{77} & \color{Custom0_8}{81} & \color{Custom0_9}{85} \\ \color{Custom1_0}{62} & \color{Custom1_1}{70} & \color{Custom1_2}{72} & \color{Custom1_3}{73} & \color{Custom1_4}{77} & \color{Custom1_5}{81} & \color{Custom1_6}{85} & \color{Custom1_7}{89} & \color{Custom1_8}{90} & \color{Custom1_9}{93} \\ \color{Custom2_0}{63} & \color{Custom2_1}{71} & \color{Custom2_2}{73} & \color{Custom2_3}{75} & \color{Custom2_4}{79} & \color{Custom2_5}{82} & \color{Custom2_6}{88} & \color{Custom2_7}{93} & \color{Custom2_8}{96} & \color{Custom2_9}{97} \\ \color{Custom3_0}{63} & \color{Custom3_1}{81} & \color{Custom3_2}{83} & \color{Custom3_3}{84} & \color{Custom3_4}{86} & \color{Custom3_5}{89} & \color{Custom3_6}{92} & \color{Custom3_7}{96} & \color{Custom3_8}{98} & \color{Custom3_9}{\bf{100}} \\ \color{Custom4_0}{72} & \color{Custom4_1}{84} & \color{Custom4_2}{85} & \color{Custom4_3}{87} & \color{Custom4_4}{89} & \color{Custom4_5}{90} & \color{Custom4_6}{94} & \color{Custom4_7}{97} & \color{Custom4_8}{102} & \color{Custom4_9}{106} \\ \color{Custom5_0}{78} & \color{Custom5_1}{85} & \color{Custom5_2}{86} & \color{Custom5_3}{91} & \color{Custom5_4}{94} & \color{Custom5_5}{97} & \color{Custom5_6}{\bf{100}} & \color{Custom5_7}{101} & \color{Custom5_8}{103} & \color{Custom5_9}{110} \\ \color{Custom6_0}{87} & \color{Custom6_1}{90} & \color{Custom6_2}{94} & \color{Custom6_3}{96} & \color{Custom6_4}{\bf{100}} & \color{Custom6_5}{101} & \color{Custom6_6}{104} & \color{Custom6_7}{108} & \color{Custom6_8}{111} & \color{Custom6_9}{114} \\ \color{Custom7_0}{90} & \color{Custom7_1}{\bf{100}} & \color{Custom7_2}{101} & \color{Custom7_3}{105} & \color{Custom7_4}{106} & \color{Custom7_5}{110} & \color{Custom7_6}{111} & \color{Custom7_7}{113} & \color{Custom7_8}{116} & \color{Custom7_9}{120} \\ \color{Custom8_0}{94} & \color{Custom8_1}{103} & \color{Custom8_2}{106} & \color{Custom8_3}{110} & \color{Custom8_4}{111} & \color{Custom8_5}{114} & \color{Custom8_6}{117} & \color{Custom8_7}{121} & \color{Custom8_8}{122} & \color{Custom8_9}{125} \\ \color{Custom9_0}{95} & \color{Custom9_1}{111} & \color{Custom9_2}{115} & \color{Custom9_3}{117} & \color{Custom9_4}{119} & \color{Custom9_5}{122} & \color{Custom9_6}{125} & \color{Custom9_7}{127} & \color{Custom9_8}{128} & \color{Custom9_9}{130} \end{matrix} \)

Разобьём решение на два этапа: широкую фазу и узкую фазу. Во время первой фазы примерно найдём, на каких диагоналях могут находиться искомые элементы (ссылка на полный исходный код — внизу страницы).

Coordinates coordiantes{ 0, 0 };

int difference{ INT_MAX };

const size_t coefficientOfProportionality{ static_cast<size_t>(

    static_cast<float>(numCols) / static_cast<float>(numRows)) };

for (size_t i{ step }; i < numRows; i += step)

{

    const size_t j{ i * coefficientOfProportionality };

    const int currentDifference{ abs(matrix[i][j] - value) };

    if (currentDifference < difference)

    {

        difference = currentDifference;

        coordiantes = Coordinates{ i, j };

    }

}

Так мы нашли некоторую ячейку на диагонали, а затем напишем простую логику вычисления координат нижней левой ячейки этой диагонали (чтобы на следующем этапе двигаться снизу вверх по диагонали).

const auto sum{ coordiantes.x + coordiantes.y };

return Coordinates{

    (sum < numRows ? sum : numRows - 1),

    (sum < numRows ?  0  : sum - numRows + 1)};

Отталкиваемся от выбранной диагонали. Изучаем сначала её, затем двигаемся к следующей и так далее. Когда просматриваем диагональ, проверяем две вещи. Первая — равно ли значение ячейки искомому значению? Вторая вещь — есть ли смысл изучать следующую диагональ? При движении вправо и вниз нужно проверять, содержит ли какая-либо ячейка числа, которые меньше либо равны искомому значению (при движении влево и вверх — соответственно, больше либо равны).

auto exploreDiagonals{ [&](Coordinates coordinates,

    auto operation, Direction direction) {

    bool done{};

    do

    {

        done = true;

        // Движение вдоль диагонали.

        for (size_t i = coordinates.x, j = coordinates.y;

            i != -1 && i < numRows && j != -1 && j < numCols;

            --i, ++j)

        {

            if (matrix[i][j] == value)

            {

                results.push_back(Coordinates{ i, j });

            }

            // Нужно ли идти дальше и исследовать другие диагонали?

            // При движении вправо и вниз нужно проверять, содержит ли какая-либо

            // ячейка числа <= "value". Если да, то продолжаем.

            if (operation(matrix[i][j], value) && done)

            {

                done = false;

            }

        }

        nextDiagonal(coordinates, direction);

    } while (!done);

} };

У нас есть два направления движения: «вправо и вниз» и «влево и вверх».

enum class Direction

{

    RightAndDown,

    LeftAndUp

};

Аргумент auto operation немного хитрее. При движении вправо и вниз нужно проверять:

if (matrix[i][j] <= value && done)

При движении влево и вверх:

if (matrix[i][j] >= value && done)

То есть разница лишь в знаке. Чтобы не повторяться, достаточно написать:

if (operation(matrix[i][j] <= value) && done)

И передавать либо std::less_equal<int>(), либо std::greater_equal<int>(). То есть сначала идём вправо и вниз, затем влево и вверх.

exploreDiagonals(start, std::less_equal<int>(), Direction::RightAndDown);

nextDiagonal(start, Direction::LeftAndUp); // Первую диагональ не нужно проверять дважды.

exploreDiagonals(start, std::greater_equal<int>(), Direction::LeftAndUp);

\( \definecolor{CustomZ}{RGB}{165,165,165} \begin{matrix} \color{CustomZ}{60} & \color{CustomZ}{64} & \color{CustomZ}{66} & \color{CustomZ}{67} & \color{CustomZ}{71} & \color{CustomZ}{75} & \color{CustomZ}{76} & \color{CustomZ}{77} & 81 & 85 \\ \color{CustomZ}{62} & \color{CustomZ}{70} & \color{CustomZ}{72} & \color{CustomZ}{73} & \color{CustomZ}{77} & \color{CustomZ}{81} & \color{CustomZ}{85} & 89 & 90 & 93 \\ \color{CustomZ}{63} & \color{CustomZ}{71} & \color{CustomZ}{73} & \color{CustomZ}{75} & \color{CustomZ}{79} & \color{CustomZ}{82} & 88 & 93 & 96 & 97 \\ \color{CustomZ}{63} & \color{CustomZ}{81} & \color{CustomZ}{83} & \color{CustomZ}{84} & \color{CustomZ}{86} & 89 & 92 & 96 & 98 & \bf{100} \\ \color{CustomZ}{72} & \color{CustomZ}{84} & \color{CustomZ}{85} & \color{CustomZ}{87} & 89 & 90 & 94 & 97 & 102 & \color{CustomZ}{106} \\ \color{CustomZ}{78} & \color{CustomZ}{85} & \color{CustomZ}{86} & 91 & 94 & 97 & \bf{100} & 101 & \color{CustomZ}{103} & \color{CustomZ}{110} \\ \color{CustomZ}{87} & \color{CustomZ}{90} & 94 & 96 & \bf{100} & 101 & 104 & \color{CustomZ}{108} & \color{CustomZ}{111} & \color{CustomZ}{114} \\ \color{CustomZ}{90} & \bf{100} & 101 & 105 & 106 & 110 & \color{CustomZ}{111} & \color{CustomZ}{113} & \color{CustomZ}{116} & \color{CustomZ}{120} \\ 94 & 103 & 106 & 110 & 111 & \color{CustomZ}{114} & \color{CustomZ}{117} & \color{CustomZ}{121} & \color{CustomZ}{122} & \color{CustomZ}{125} \\ 95 & 111 & 115 & 117 & \color{CustomZ}{119} & \color{CustomZ}{122} & \color{CustomZ}{125} & \color{CustomZ}{127} & \color{CustomZ}{128} & \color{CustomZ}{130} \end{matrix} \)

Широкая фаза нашла ячейку (5, 5), нижняя левая ячейка этой диагонали имеет координаты (9, 1). Во время узкой фазы в матрице из ста элементов пришлось исследовать 57 элементов: 43 выделены, ещё 14 находятся на ближайших диагоналях. Всего пришлось изучить 7 диагоналей (выделены пять из них). Найденные ячейки имеют верные координаты.

Для проверки можно написать поиск методом полного перебора.

for (size_t i{ 0 }; i < numRows; ++i)

{

    for (size_t j{ 0 }; j < numCols; ++j)

    {

        if (matrix[i][j] == value)

        {

            results.push_back(Coordinates{ i, j });

        }

    }

}

Эвристический поиск при равномерном распределении значений в матрице и удачно подобранном шаге во время широкой фазы покажет хорошие результаты.

Приложение: исходный код.

23 апреля 2020