lphw/bsearch.vbs at master · sitrucz1/lphw · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
'
' Bsearch and Interpolation Search routines
'

option explicit

sub main()
    dim arr(999) ' : arr = array(1, 4, 5, 6, 7, 9, 12, 14, 15, 17, 19) ' arr = array(1, 3, 5, 7, 8, 9) ' arr = array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
    dim timerstart, timerend, i
    for i = 0 to 999 step 1
        arr(i) = int(i*1.5)
    next
    wscript.echo join(arr)
    timerstart = timer
    wscript.echo bsearch(arr, 7)
    wscript.echo bsearch(arr, 0)
    wscript.echo bsearch(arr, 17)
    wscript.echo bsearch(arr, 4)
    wscript.echo bsearch(arr, 6)
    timerend = timer
    wscript.echo "timer => ", timerend - timerstart
    timerstart = timer
    wscript.echo bsearch2(arr, 7)
    wscript.echo bsearch2(arr, 0)
    wscript.echo bsearch2(arr, 17)
    wscript.echo bsearch2(arr, 4)
    wscript.echo bsearch2(arr, 6)
    timerend = timer
    wscript.echo "timer => ", timerend - timerstart
    timerstart = timer
    wscript.echo bsearch3(arr, 7)
    wscript.echo bsearch3(arr, 0)
    wscript.echo bsearch3(arr, 17)
    wscript.echo bsearch3(arr, 4)
    wscript.echo bsearch3(arr, 6)
    timerend = timer
    wscript.echo "timer => ", timerend - timerstart
    timerstart = timer
    wscript.echo intbsearch(arr, 7)
    wscript.echo intbsearch(arr, 0)
    wscript.echo intbsearch(arr, 17)
    wscript.echo intbsearch(arr, 4)
    wscript.echo intbsearch(arr, 6)
    timerend = timer
    wscript.echo "timer => ", timerend - timerstart
end sub

function bsearch(arr, key)
    dim lo, hi, idx
    lo = 0 : hi = ubound(arr)
    idx = lo + (hi - lo) \ 2
    do while lo < hi and key <> arr(idx)
        wscript.echo "idx => ", idx
        if key < arr(idx) then
            hi = idx-1
        else
            lo = idx+1
        end if
        idx = lo + (hi - lo) \ 2
    loop
    if key = arr(idx) then
        bsearch = idx
    else
        bsearch = -1
    end if
end function

function bsearch2(arr, key)
    dim lo, hi, idx
    lo = 0 : hi = ubound(arr)
    do while lo < hi
        idx = lo + (hi - lo) \ 2
        wscript.echo "idx => ", idx
        if key <= arr(idx) then
            hi = idx
        else
            lo = idx+1
        end if
    loop
    if key = arr(lo) then
        bsearch2 = lo
    else
        bsearch2 = -1
    end if
end function

function bsearch3(arr, key)
    dim lo, hi, idx
    lo = 0 : hi = ubound(arr)
    do while lo <= hi
        idx = lo + (hi - lo) \ 2
        wscript.echo "idx => ", idx
        if key < arr(idx) then
            hi = idx-1
        elseif key > arr(idx) then
            lo = idx+1
        else
            bsearch3 = idx
            exit function
        end if
    loop
    bsearch3 = -1
end function

function intbsearch(arr, key)
    dim lo, hi, idx
    lo = 0 : hi = ubound(arr)
    do while arr(lo) <> arr(hi) and arr(lo) <= key and key <= arr(hi)
        idx = int(lo + (key - arr(lo)) / (arr(hi) - arr(lo)) * (hi - lo))
        wscript.echo "idx => ", idx
        if key = arr(idx) then
            intbsearch = idx
            exit function
        elseif key < arr(idx) then
            hi = idx-1
        else
            lo = idx+1
        end if
    loop
    if key = arr(lo) then
        intbsearch = lo
    else
        intbsearch = -1
    end if
end function

call main()