Условие: Номер 2

Задача 2. Задан массив чисел А[1:N,1:M],упорядоченный по возрастанию по строкам и столбцам, т.е.: А[I,1]<А[I,2]<...<А[I,M] (при всех I), А[1,J]<A[2,J]<...<А[N,J] (при всех J). Найти элемент массива, равный заданному числу Х и отпечатать его индексы (I,J). Напечатать слово "НЕТ", если такого элемента не окажется. Х можно сравнить не более, чем с M+N элементами массива.

  Решение задачи: Номер 2

Решение задачи 2. Простейшим решением является просмотр элементов массива до нахождения требуемого элемента или установления факта, что такого элемента нет. Очевидно, что в последнем случае необходим просмотр всех элементов массива. Однако возможно существенно сократить количество операций, используя следующий факт. Рассмотрим элемент A[1,m]. Возможны следующие ситуации: 1. X = A[1,m]. В этом случае заданный элемент найден. 2. X < A[1,m]. В этом случае легко заметить, что элемента, равного X, в столбце с номером M быть не может. Поэтому можно ограничится по иском заданного элемента в подматрице без M-того столбца. 3. X > A[1,m]. В этом случае легко заметить, что элемента, равного X, в строке с номером 1 быть не может. Поэтому можно ограничится по иском заданного элемента в подматрице без 1-той строки. Таким образом, сравнивая на каждом шаге значение заданного элемента X со значением элемента, расположенного в правом верхнем углу интересующей нас подматрицы, суммарное число строк и столбцов интересующей нас подматрицы уменьшается на 1. Поэтому трудоемкость такого поиска не превосходит N+M.

Назад