Поиск делением пополам

MODULE  ADruS18_Поиск;  (* Иллюстрация алгоритмов поиска *)

    IMPORT  Log := StdLog,  In := i21sysIn,  R := ObxRandom;
    
    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; (* кол-во элементов, среди которых ищем *)
            n: INTEGER; (* позиция искомого значения *)
            x: INTEGER; (* искомое значение или "аргумент поиска" *)
            L, R, m: INTEGER;
            found: BOOLEAN;
    BEGIN
        Log.Ln;
        Log.String('Проверяем поиск делением пополам:');  Log.Ln;
        
        N := 100000;
        n := ( 3 * N ) DIV 4;
        
        (* Пример 1. В массиве нет искомого значения *)
        NEW( a, N );
        InitSorted( a ); (* возрастающие положительные *)
        x := 0;
        
        (***********************************)
        L := 0;  R := N - 1;  found := FALSE;
        WHILE ( L <= R ) & ~found DO
            m := ( L + R ) DIV 2; (* любое значение между L и R *)
            IF  a[ m ] = x  THEN
                found :=  TRUE
            ELSIF  a[ m ] < x  THEN
                L := m + 1
            ELSE
                R := m - 1
            END
        END;
        (****************************************************)
        ASSERT( ~found ); (* не нашли *)
        Log.String('Выполнен пример 1.');  Log.Ln;
        
        (* Пример 2. В массиве ровно одно искомое значение *)
        NEW( a, N );
        InitSorted( a ); (* возрастающие положительные *)
        x := a[ n ]; (* искомое значение в массиве *)
        
        L := 0;  R := N - 1;  found := FALSE;
        WHILE ( L <= R ) & ~found DO
            m := ( L + R ) DIV 2; (* любое значение между L и R *)
            IF  a[ m ] = x  THEN
                found :=  TRUE
            ELSIF  a[ m ] < x  THEN
                L := m + 1
            ELSE
                R := m - 1
            END
        END;
        ASSERT( m = n ); (* т.е. успешно нашли позицию значения x *)
        Log.String('Выполнен пример 2.');  Log.Ln;
        
        (* Пример 3. В массиве искомое значение в нескольких экземплярах *)
        NEW( a, N );
        InitSorted( a ); (* возрастающие положительные *)
        x := a[ n ]; (* искомое значение в массиве *)
        a[ n+1 ] := x; (* чтобы усложнить жизнь *)
        a[ n-1 ] := x; (* чтобы усложнить жизнь *)
        
        L := 0;  R := N - 1;  found := FALSE;
        WHILE ( L <= R ) & ~found DO
            m := ( L + R ) DIV 2; (* любое значение между L и R *)
            IF  a[ m ] = x  THEN
                found :=  TRUE
            ELSIF  a[ m ] < x  THEN
                L := m + 1
            ELSE
                R := m - 1
            END
        END;
        ASSERT( ( m = n ) OR ( m = n-1 ) OR ( m = n+1) ); (* т.е. успешно нашли позицию значения x *)
        Log.Int( n );  Log.Int( m );  Log.Ln;
        Log.String('Выполнен пример 3.');  Log.Ln;
        
        (* Пример 4. Немного ускоренный вариант *)
        NEW( a, N );
        InitSorted( a ); (* возрастающие положительные *)
        x := a[ n ]; (* искомое значение в массиве *)

        (**********************************)
        L := 0;  R := N;
        WHILE  L < R  DO
            m := (L+R) DIV 2;
            IF a[m] < x THEN L := m+1 ELSE R := m END
        END;
        (****************************************************)
        ASSERT( ( L = n ) OR ( L = n+1) );
        Log.Int( n );  Log.Int( L );  Log.Ln;
        Log.String('Выполнен пример 4.');  Log.Ln;
    
    END ДелениемПополам;
    
END  ADruS18_Поиск.