' Search Algorithms — linear, binary, interpolation search
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    DIM nums(1 TO 15) AS LONG
    LOCAL i AS LONG
    LOCAL a AS LONG
    LOCAL b AS LONG
    LOCAL mid AS LONG
    LOCAL pos AS LONG
    LOCAL found AS LONG
    LOCAL n AS LONG
    LOCAL target AS LONG
    LOCAL outLine AS STRING
    LOCAL keepGoing AS LONG

    PRINT "=========================="
    PRINT " Search Algorithms"
    PRINT "=========================="
    PRINT

    n = 10
    nums(1) = 17
    nums(2) = 42
    nums(3) = 3
    nums(4) = 88
    nums(5) = 55
    nums(6) = 24
    nums(7) = 99
    nums(8) = 13
    nums(9) = 61
    nums(10) = 7

    PRINT "=== LINEAR SEARCH ==="
    target = 55
    found = -1
    FOR i = 1 TO n
        IF nums(i) = target THEN
            found = i
            EXIT FOR
        END IF
    NEXT i
    PRINT "Search for 55: index " + STR$(found)

    target = 100
    found = -1
    FOR i = 1 TO n
        IF nums(i) = target THEN
            found = i
            EXIT FOR
        END IF
    NEXT i
    PRINT "Search for 100: index " + STR$(found)
    PRINT

    n = 10
    nums(1) = 3
    nums(2) = 7
    nums(3) = 13
    nums(4) = 17
    nums(5) = 24
    nums(6) = 42
    nums(7) = 55
    nums(8) = 61
    nums(9) = 88
    nums(10) = 99

    PRINT "=== BINARY SEARCH (sorted array) ==="
    target = 42
    a = 1
    b = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF a > b THEN EXIT DO
        mid = (a + b) / 2
        IF nums(mid) = target THEN
            found = mid
            EXIT DO
        END IF
        IF nums(mid) < target THEN
            a = mid + 1
        ELSE
            b = mid - 1
        END IF
    LOOP
    PRINT "Search for 42: index " + STR$(found)

    target = 3
    a = 1
    b = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF a > b THEN EXIT DO
        mid = (a + b) / 2
        IF nums(mid) = target THEN
            found = mid
            EXIT DO
        END IF
        IF nums(mid) < target THEN
            a = mid + 1
        ELSE
            b = mid - 1
        END IF
    LOOP
    PRINT "Search for 3: index " + STR$(found)

    target = 99
    a = 1
    b = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF a > b THEN EXIT DO
        mid = (a + b) / 2
        IF nums(mid) = target THEN
            found = mid
            EXIT DO
        END IF
        IF nums(mid) < target THEN
            a = mid + 1
        ELSE
            b = mid - 1
        END IF
    LOOP
    PRINT "Search for 99: index " + STR$(found)

    target = 50
    a = 1
    b = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF a > b THEN EXIT DO
        mid = (a + b) / 2
        IF nums(mid) = target THEN
            found = mid
            EXIT DO
        END IF
        IF nums(mid) < target THEN
            a = mid + 1
        ELSE
            b = mid - 1
        END IF
    LOOP
    PRINT "Search for 50: index " + STR$(found) & " (not found)"
    PRINT

    n = 10
    nums(1) = 10
    nums(2) = 20
    nums(3) = 30
    nums(4) = 40
    nums(5) = 50
    nums(6) = 60
    nums(7) = 70
    nums(8) = 80
    nums(9) = 90
    nums(10) = 100

    PRINT "=== INTERPOLATION SEARCH ==="
    target = 30
    a = 1
    b = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF a > b THEN EXIT DO
        IF target < nums(a) THEN EXIT DO
        IF target > nums(b) THEN EXIT DO
        IF nums(b) = nums(a) THEN EXIT DO
        pos = a + ((target - nums(a)) * (b - a)) / (nums(b) - nums(a))
        IF pos < 1 OR pos > n THEN EXIT DO
        IF nums(pos) = target THEN
            found = pos
            EXIT DO
        END IF
        IF nums(pos) < target THEN
            a = pos + 1
        ELSE
            b = pos - 1
        END IF
    LOOP
    PRINT "Search for 30: index " + STR$(found)

    target = 80
    a = 1
    b = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF a > b THEN EXIT DO
        IF target < nums(a) THEN EXIT DO
        IF target > nums(b) THEN EXIT DO
        IF nums(b) = nums(a) THEN EXIT DO
        pos = a + ((target - nums(a)) * (b - a)) / (nums(b) - nums(a))
        IF pos < 1 OR pos > n THEN EXIT DO
        IF nums(pos) = target THEN
            found = pos
            EXIT DO
        END IF
        IF nums(pos) < target THEN
            a = pos + 1
        ELSE
            b = pos - 1
        END IF
    LOOP
    PRINT "Search for 80: index " + STR$(found)

    target = 100
    a = 1
    b = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF a > b THEN EXIT DO
        IF target < nums(a) THEN EXIT DO
        IF target > nums(b) THEN EXIT DO
        IF nums(b) = nums(a) THEN EXIT DO
        pos = a + ((target - nums(a)) * (b - a)) / (nums(b) - nums(a))
        IF pos < 1 OR pos > n THEN EXIT DO
        IF nums(pos) = target THEN
            found = pos
            EXIT DO
        END IF
        IF nums(pos) < target THEN
            a = pos + 1
        ELSE
            b = pos - 1
        END IF
    LOOP
    PRINT "Search for 100: index " + STR$(found)

    target = 55
    a = 1
    b = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF a > b THEN EXIT DO
        IF target < nums(a) THEN EXIT DO
        IF target > nums(b) THEN EXIT DO
        IF nums(b) = nums(a) THEN EXIT DO
        pos = a + ((target - nums(a)) * (b - a)) / (nums(b) - nums(a))
        IF pos < 1 OR pos > n THEN EXIT DO
        IF nums(pos) = target THEN
            found = pos
            EXIT DO
        END IF
        IF nums(pos) < target THEN
            a = pos + 1
        ELSE
            b = pos - 1
        END IF
    LOOP
    PRINT "Search for 55: index " + STR$(found) & " (not found)"
    PRINT

    n = 15
    FOR i = 1 TO 15
        nums(i) = i * 5
    NEXT i
    PRINT "=== SEARCH COMPARISON ==="
    target = 45
    found = -1
    FOR i = 1 TO n
        IF nums(i) = target THEN
            found = i
            EXIT FOR
        END IF
    NEXT i
    PRINT "Linear: index " + STR$(found)

    a = 1
    b = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF a > b THEN EXIT DO
        mid = (a + b) / 2
        IF nums(mid) = target THEN
            found = mid
            EXIT DO
        END IF
        IF nums(mid) < target THEN
            a = mid + 1
        ELSE
            b = mid - 1
        END IF
    LOOP
    PRINT "Binary: index " + STR$(found)

    a = 1
    b = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF a > b THEN EXIT DO
        IF target < nums(a) THEN EXIT DO
        IF target > nums(b) THEN EXIT DO
        IF nums(b) = nums(a) THEN EXIT DO
        pos = a + ((target - nums(a)) * (b - a)) / (nums(b) - nums(a))
        IF pos < 1 OR pos > n THEN EXIT DO
        IF nums(pos) = target THEN
            found = pos
            EXIT DO
        END IF
        IF nums(pos) < target THEN
            a = pos + 1
        ELSE
            b = pos - 1
        END IF
    LOOP
    PRINT "Interpolation: index " + STR$(found)
    PRINT

    PRINT "Search algorithms complete."
    FUNCTION = 0
END FUNCTION
