Files
alexm e092cb029c
Build, test, deploy / site (push) Failing after 15m13s
Initial commit
2026-11-12 22:24:02 -05:00

25 lines
741 B
Plaintext

// CALL: CONTAINS_SORTED([2, 5, 8, 13, 21], 13)
// EXPECT: CONTAINS_SORTED returned TRUE
// Is X in the sorted list L? Halve the range that could hold it each time.
FUNCTION CONTAINS_SORTED(L : LIST OF INTEGER, X : INTEGER) RETURNS BOOL
REQUIRE FORALL K IN [0, LENGTH(L) - 1) : L[K] <= L[K + 1]
DECLARE Lo : INTEGER
DECLARE Hi : INTEGER
DECLARE Mid : INTEGER
Lo <- 0
Hi <- LENGTH(L)
WHILE Lo < Hi
INVARIANT 0 <= Lo AND Lo <= Hi AND Hi <= LENGTH(L)
DECREASES Hi - Lo
Mid <- (Lo + Hi) DIV 2
IF L[Mid] == X THEN
RETURN TRUE
ELSEIF L[Mid] < X THEN
Lo <- Mid + 1
ELSE
Hi <- Mid
ENDIF
ENDWHILE
RETURN FALSE
ENDFUNCTION