Задача 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.
Простейшим решением является просмотр элементов массива до нахождения требуемого элемента или установления факта, что такого элемента нет. Очевидно, что в последнем случае необходим просмотр всех элементов массива.
Однако возможно существенно сократить количество операций, используя следующий факт.
Рассмотрим элемент 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.
|
