Задача на линейный поиск, помогите найти ошибку Опции

[dog]

1. Дан двумерный массив A [NxM] , элементы которого меняются по определенному закону. Определить, есть ли в массиве элемент со значением Q.

PROGRAM PRPV1;
const n=3;m=3;
type Tarr = Array[1..n,1..m] of real;
var
A:Tarr;

i,j:BYTE;
q:real;



BEGIN
    FOR i:=1 TO n DO
    FOR j:=1 TO m DO
    A[i,j]:=30*(n+1-j)+0.2*i; {закон изменения элементов}

    FOR i:=1 TO n DO {вывод массива на печать}
    BEGIN
        FOR j:=1 TO m DO
        WRITE(A[i,j]:0:2,' ');
        WRITELN;
    END;

    WRITELN('Enter Q'); {ввод значения для поиска}
    READLN(q); {до сюда все работает идеально}

    i:=1;
    j:=1;
    WHILE((i<=n) and (A[i,j]<>q)) do {проблемы начинаются тут}
    begin
    WHILE((i<=m) and (A[i,j]<>q)) do
    j:=j+1;
    IF j>m then
    i:=i+1;
    end;

    IF (i > n) AND (j > m) THEN {вывод на печать найденного элемента или сообщение об отсутствии элемента}
       WRITELN('not found')
    ELSE
       WRITELN('found A[',i,',',j,']');

END.

Программа работает идеально, ищет элементы выводит их индексы. Но когда задаешь элемент, которого нет в массиве программа зависает.

Сообщение отредактировано: dog - 1.04.2010 4:06

[volvo]

просто объясните на каком-нибудь примере как делать бинарный поиск в условиях двумерного массива.

А точно так же, как и в условиях одномерного массива. Дело все в том, что при наличии двумерной матрицы мы в любое время и для любого элемента можем получить смещение этого элемента от начала массива, правда? Нам же известны номер строки и номер столбца, а также число элементов в строке. Обратное преобразование (из смещения относительно начала в номера строки и столбца) - тоже делается очень просто. Это все, что нужно.

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

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