Линейный поиск

MODULE  ADruS18_Поиск;  

    IMPORT  Log := StdLog,  In := i21sysIn,  R := ObxRandom;
    
    PROCEDURE InitRandom ( OUT a: ARRAY OF INTEGER ); (* инициализация массива случайными числами *)
        VAR  i: INTEGER;
    BEGIN
        R.InitSeed( 12345 );
        FOR  i := 0  TO  LEN( a )  - 1  DO
            a[ i ] := 1 + SHORT( ENTIER( ( LEN( a ) )* R.Uniform() ) );
            ASSERT( a[ i ] > 0 ); (* гарантируем инициализацию только положительными числами *)
        END;
    END InitRandom;
    
    PROCEDURE InitSorted ( OUT a: ARRAY OF INTEGER ); (* инициализация массива упорядоченными числами *)
        VAR  i: INTEGER;
    BEGIN
        FOR  i := 0  TO  LEN( a ) - 1  DO
            a[ i ] := 1 + i ; 
            ASSERT( a[ i ] > 0 ); (* гарантируем инициализацию только положительными числами *)
        END;
    END InitSorted;
    
    
    PROCEDURE Линейный*; 
        VAR
            a: POINTER TO ARRAY OF INTEGER; (* указатель на массив, в котором поиск *)
            N: INTEGER; (* кол-во элементов, среди которых ищем *)
            x: INTEGER; (* искомое значение или "аргумент поиска" *)
            i: INTEGER;
            
            a1, a2, a3, a4: POINTER TO ARRAY OF INTEGER;
    BEGIN
        Log.Ln;
        Log.String('Проверяем примеры линейного поиска:');  Log.Ln;
        
        N := 10;
        x := 0;  (* в примерах будем всегда искать значение нуль *)
        
        (* в каждом примере размещаем новый массив а, но запоминаем указатель на него, чтобы иметь возможность заглянуть в содержимое массивов в конце*)
        
        (* Простейший линейный поиск *)
        
        (* Пример 1. Искомое значение присутствует в массиве *)
        NEW( a, N );
                            a1 := a;  (* запомнили указатель, чтобы в конце посмотреть на массив *)
        InitRandom( a );
        a[ 5 ] := 0;
        a[ 8 ] := 0; (* помещаем дважды, найдется первое вхождение *)
        
        (* собственно поиск: ****************)
        i := 0; 
        WHILE ( i < N ) & ( a[ i ] # x ) DO  INC( i )  END;
        (* конец фрагмента. ***************************************************)
        
        ASSERT( i = 5 ); (* нашли наименьшую позицию *)
        Log.String('Выполнен пример 1.');  Log.Ln;
        
        (* Пример 2. Искомого значения в массиве нет *)
        NEW( a, N );
                            a2 := a;  (* запомнили указатель, чтобы в конце посмотреть на массив *)
        InitRandom( a );
        
        i := 0; 
        WHILE ( i < N ) & ( a[ i ] # x ) DO  INC( i )  END;

        ASSERT( i = N ); (* не нашли *)
        Log.String('Выполнен пример 2.');  Log.Ln;
        
        (* Линейный поиск с барьером *)
        
        (* Пример 3. Искомое значение присутствует в массиве *)
        NEW( a, N + 1 ); (* нужен один лишний элемент для барьера *)
                            a3 := a;  (* запомнили указатель, чтобы в конце посмотреть на массив *)
        InitRandom( a );
        a[ 5 ] := 0;
        
        a[ N ] := 0; (* выставили барьер *)
        i := 0; 
        WHILE  a[ i ] # x  DO  INC( i )  END;
        ASSERT( i = 5 ); (* нашли наименьшую позицию *)
        Log.String('Выполнен пример 3.');  Log.Ln;
        
        (* Пример 4. Искомого значения в массиве нет *)
        NEW( a, N + 1 ); (* нужен один лишний элемент для барьера *)
                            a4 := a;  (* запомнили указатель, чтобы в конце посмотреть на массив *)
        InitRandom( a ); (* в массиве только положит. числа *)

        (********************************)
        a[ N ] := x;  i := 0; 
        WHILE  a[ i ] # x  DO  INC( i )  END;
        (****************************************************)
        ASSERT( i = N ); (* нашли только сам барьер *)
        Log.String('Выполнен пример 4.');  Log.Ln;
        
        a := NIL;
        HALT( 0 ); (* чтобы заглянуть в содержимое всех 4х массивов, кликать по синим ромбам и черным стрелочкам в окошке Трапа *)
    END Линейный;
    
END  ADruS18_Поиск.