' Array Search & Sort — binary search, interpolation search on sorted arrays
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    DIM nums(1 TO 100) AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL temp AS LONG
    LOCAL n AS LONG
    LOCAL lo AS LONG
    LOCAL hi AS LONG
    LOCAL mid AS LONG
    LOCAL pos AS LONG
    LOCAL found AS LONG
    LOCAL target AS LONG
    LOCAL line AS STRING
    LOCAL keepGoing AS LONG

    PRINT "=============================="
    PRINT " Array Search & Sort"
    PRINT "=============================="
    PRINT

    n = 15
    nums(1) = 2
    nums(2) = 5
    nums(3) = 8
    nums(4) = 12
    nums(5) = 16
    nums(6) = 23
    nums(7) = 38
    nums(8) = 45
    nums(9) = 56
    nums(10) = 67
    nums(11) = 78
    nums(12) = 89
    nums(13) = 92
    nums(14) = 97
    nums(15) = 99

    PRINT "=== BINARY SEARCH ==="
    PRINT "Sorted array: 2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78, 89, 92, 97, 99"
    target = 45
    lo = 1
    hi = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF lo > hi THEN EXIT DO
        mid = (lo + hi) / 2
        IF nums(mid) = target THEN
            found = mid
            EXIT DO
        END IF
        IF nums(mid) < target THEN
            lo = mid + 1
        ELSE
            hi = mid - 1
        END IF
    LOOP
    PRINT "Search for 45: index " & STR$(found)
    target = 2
    lo = 1
    hi = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF lo > hi THEN EXIT DO
        mid = (lo + hi) / 2
        IF nums(mid) = target THEN
            found = mid
            EXIT DO
        END IF
        IF nums(mid) < target THEN
            lo = mid + 1
        ELSE
            hi = mid - 1
        END IF
    LOOP
    PRINT "Search for 2: index " & STR$(found)
    target = 99
    lo = 1
    hi = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF lo > hi THEN EXIT DO
        mid = (lo + hi) / 2
        IF nums(mid) = target THEN
            found = mid
            EXIT DO
        END IF
        IF nums(mid) < target THEN
            lo = mid + 1
        ELSE
            hi = mid - 1
        END IF
    LOOP
    PRINT "Search for 99: index " & STR$(found)
    target = 50
    lo = 1
    hi = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF lo > hi THEN EXIT DO
        mid = (lo + hi) / 2
        IF nums(mid) = target THEN
            found = mid
            EXIT DO
        END IF
        IF nums(mid) < target THEN
            lo = mid + 1
        ELSE
            hi = mid - 1
        END IF
    LOOP
    PRINT "Search for 50: index " & STR$(found) & " (not found)"
    PRINT

    n = 12
    FOR i = 1 TO 12
        nums(i) = i * 10
    NEXT i
    PRINT "=== INTERPOLATION SEARCH ==="
    PRINT "Array: 10, 20, 30, ..., 120"
    target = 30
    lo = 1
    hi = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF lo > hi THEN EXIT DO
        IF target < nums(lo) THEN EXIT DO
        IF target > nums(hi) THEN EXIT DO
        IF nums(hi) = nums(lo) THEN EXIT DO
        pos = lo + ((target - nums(lo)) * (hi - lo)) / (nums(hi) - nums(lo))
        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
            lo = pos + 1
        ELSE
            hi = pos - 1
        END IF
    LOOP
    PRINT "Search for 30: index " & STR$(found)
    target = 100
    lo = 1
    hi = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF lo > hi THEN EXIT DO
        IF target < nums(lo) THEN EXIT DO
        IF target > nums(hi) THEN EXIT DO
        IF nums(hi) = nums(lo) THEN EXIT DO
        pos = lo + ((target - nums(lo)) * (hi - lo)) / (nums(hi) - nums(lo))
        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
            lo = pos + 1
        ELSE
            hi = pos - 1
        END IF
    LOOP
    PRINT "Search for 100: index " & STR$(found)
    target = 55
    lo = 1
    hi = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF lo > hi THEN EXIT DO
        IF target < nums(lo) THEN EXIT DO
        IF target > nums(hi) THEN EXIT DO
        IF nums(hi) = nums(lo) THEN EXIT DO
        pos = lo + ((target - nums(lo)) * (hi - lo)) / (nums(hi) - nums(lo))
        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
            lo = pos + 1
        ELSE
            hi = pos - 1
        END IF
    LOOP
    PRINT "Search for 55: index " & STR$(found) & " (not found)"
    PRINT

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

    PRINT "=== SORT THEN SEARCH ==="
    PRINT "Before sort:"
    line = ""
    FOR i = 1 TO n
        line = line & STR$(nums(i)) & " "
    NEXT i
    PRINT line

    FOR i = 1 TO n - 1
        FOR j = 1 TO n - i
            IF nums(j) > nums(j + 1) THEN
                temp = nums(j)
                nums(j) = nums(j + 1)
                nums(j + 1) = temp
            END IF
        NEXT j
    NEXT i
    PRINT "After sort:  "
    line = ""
    FOR i = 1 TO n
        line = line & STR$(nums(i)) & " "
    NEXT i
    PRINT line

    target = 55
    lo = 1
    hi = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF lo > hi THEN EXIT DO
        mid = (lo + hi) / 2
        IF nums(mid) = target THEN
            found = mid
            EXIT DO
        END IF
        IF nums(mid) < target THEN
            lo = mid + 1
        ELSE
            hi = mid - 1
        END IF
    LOOP
    PRINT "Binary search for 55: index " & STR$(found)
    target = 42
    lo = 1
    hi = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF lo > hi THEN EXIT DO
        mid = (lo + hi) / 2
        IF nums(mid) = target THEN
            found = mid
            EXIT DO
        END IF
        IF nums(mid) < target THEN
            lo = mid + 1
        ELSE
            hi = mid - 1
        END IF
    LOOP
    PRINT "Binary search for 42: index " & STR$(found)
    target = 100
    lo = 1
    hi = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF lo > hi THEN EXIT DO
        mid = (lo + hi) / 2
        IF nums(mid) = target THEN
            found = mid
            EXIT DO
        END IF
        IF nums(mid) < target THEN
            lo = mid + 1
        ELSE
            hi = mid - 1
        END IF
    LOOP
    PRINT "Binary search for 100: index " & STR$(found) & " (not found)"
    PRINT

    n = 100
    FOR i = 1 TO 100
        nums(i) = i * 2
    NEXT i
    FOR i = 1 TO n - 1
        FOR j = 1 TO n - i
            IF nums(j) > nums(j + 1) THEN
                temp = nums(j)
                nums(j) = nums(j + 1)
                nums(j + 1) = temp
            END IF
        NEXT j
    NEXT i
    target = 150
    PRINT "=== SEARCH SPEED COMPARISON ==="
    PRINT "Searching for " & STR$(target) & " in 100 elements"
    found = -1
    FOR i = 1 TO n
        IF nums(i) = target THEN
            found = i
            EXIT FOR
        END IF
    NEXT i
    PRINT "Linear: " & STR$(found)
    lo = 1
    hi = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF lo > hi THEN EXIT DO
        mid = (lo + hi) / 2
        IF nums(mid) = target THEN
            found = mid
            EXIT DO
        END IF
        IF nums(mid) < target THEN
            lo = mid + 1
        ELSE
            hi = mid - 1
        END IF
    LOOP
    PRINT "Binary: " & STR$(found)
    lo = 1
    hi = n
    found = -1
    keepGoing = 1
    DO WHILE keepGoing
        IF lo > hi THEN EXIT DO
        IF target < nums(lo) THEN EXIT DO
        IF target > nums(hi) THEN EXIT DO
        IF nums(hi) = nums(lo) THEN EXIT DO
        pos = lo + ((target - nums(lo)) * (hi - lo)) / (nums(hi) - nums(lo))
        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
            lo = pos + 1
        ELSE
            hi = pos - 1
        END IF
    LOOP
    PRINT "Interpolation: " & STR$(found)
    PRINT

    PRINT "Search and sort complete."
    FUNCTION = 0
END FUNCTION
