-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathArrayPlusCandidate.au3
115 lines (105 loc) · 3.31 KB
/
ArrayPlusCandidate.au3
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
#include "ArrayPlus.au3"
Global $aArray[100][3]
Local $t = -1
For $i = 0 To UBound($aArray) - 1
$t += Random(1, 100, 1) ; random to avoid to create a best-case scenario (entries from 0 to N with Step 1)
$aArray[$i][0] = $t
$aArray[$i][1] = "Teststring " & $t
Next
_ArrayDisplay($aArray)
$x = _ArrayInterpolationSearch($aArray, $aArray[80][0])
$ext = @extended
_ArrayDisplay($x, $ext)
Func _ArrayInterpolationSearch(ByRef $aArray, Const $vSearch, Const $nRow = 0, $iFrom = 0, $iTo = UBound($aArray) - 1, Const $bFuzzy = True)
Local $dx, $dy, $m, $b
Local $iMatch = -1
If UBound($aArray, 0) = 1 Then ; 1D-array
If $vSearch < $aArray[$iFrom] Then Return $bFuzzy ? SetExtended($iFrom, $aArray[$iFrom]) : SetError(1, -1, Null)
If $vSearch > $aArray[$iTo] Then Return $bFuzzy ? SetExtended($iFrom, $aArray[$iTo]) : SetError(1, -1, Null)
Do
$dx = $iTo - $iFrom
If $dx = 1 Then
If $aArray[$iTo] = $vSearch Then
$iMatch = $iTo
ElseIf $aArray[$iFrom] = $vSearch Then
$iMatch = $iFrom
EndIf
ExitLoop
EndIf
If $dx = 0 Then ExitLoop
$dy = $aArray[$iTo] - $aArray[$iFrom]
If $dy = 0 Then
If $aArray[$iFrom] = $vSearch Then
$iMatch = $iFrom
EndIf
ExitLoop
EndIf
$m = $dy / $dx
$b = Int(($vSearch - $aArray[$iFrom]) / $m)
$p = $iFrom + $b
If $aArray[$p] = $vSearch Then ; found
$iMatch = $p
ExitLoop
ElseIf $aArray[$p] > $vSearch Then
$iTo = $p - 1
Else
$iFrom = $p + 1
EndIf
Until $iFrom > $iTo
If $iMatch = -1 Then ; no match found
If $bFuzzy = True Then
Return Abs($vSearch - $aArray[$iFrom]) <= Abs($vSearch - $aArray[$iTo]) _
? SetExtended($iFrom, $aArray[$iFrom]) _
: SetExtended($iTo, $aArray[$iTo])
Else
Return SetError(1, -1, Null)
EndIf
Else ; match found
Return SetExtended($iMatch, $aArray[$iMatch])
EndIf
Else ; 2D-array
If $vSearch < $aArray[$iFrom][$nRow] Then Return $bFuzzy ? SetExtended($iFrom, _ArraySlice($aArray, "[" & $iFrom & "][:]")) : SetError(1, -1, Null)
If $vSearch > $aArray[$iTo][$nRow] Then Return $bFuzzy ? SetExtended($iTo, _ArraySlice($aArray, "[" & $iTo & "][:]")) : SetError(1, -1, Null)
Do
$dx = $iTo - $iFrom
If $dx = 1 Then
If $aArray[$iTo][$nRow] = $vSearch Then
$iMatch = $iTo
ElseIf $aArray[$iFrom][$nRow] = $vSearch Then
$iMatch = $iFrom
EndIf
ExitLoop
EndIf
If $dx = 0 Then ExitLoop
$dy = $aArray[$iTo][$nRow] - $aArray[$iFrom][$nRow]
If $dy = 0 Then
If $aArray[$iFrom][$nRow] = $vSearch Then
$iMatch = $iFrom
EndIf
ExitLoop
EndIf
$m = $dy / $dx
$b = Int(($vSearch - $aArray[$iFrom][$nRow]) / $m)
$p = $iFrom + $b
If $aArray[$p][$nRow] = $vSearch Then ; found
$iMatch = $p
ExitLoop
ElseIf $aArray[$p][$nRow] > $vSearch Then
$iTo = $p - 1
Else
$iFrom = $p + 1
EndIf
Until $iFrom > $iTo
If $iMatch = -1 Then ; no match found
If $bFuzzy = True Then
Return Abs($vSearch - $aArray[$iFrom][$nRow]) <= Abs($vSearch - $aArray[$iTo][$nRow]) _
? SetExtended($iFrom, _ArraySlice($aArray, "[" & $iFrom & "][:]")) _
: SetExtended($iTo, _ArraySlice($aArray, "[" & $iTo & "][:]"))
Else
Return SetError(1, -1, Null)
EndIf
Else ; match found
Return SetExtended($iMatch, _ArraySlice($aArray, "[" & $iMatch & "][:]"))
EndIf
EndIf
EndFunc ;==>_ArrayInterpolationSearch