# Interpolate Binary Search

## Recommended Posts

As usual binary search it seeks in a sorted array.

But instead of using O(log n) time in the average case it should use O(log log n) but it works only with numbers not with every comparable type.

;Scroll down. Check Ezzetabi's post.
Edited by ezzetabi

##### Share on other sites

Cool. Look at this example.

#include <Array.au3>
Dim \$Array[101]
\$Array[1]=100
For \$X=1 to 100
\$Array[\$X]=\$X
Next
_ArraySort(\$Array)
\$Timer=TimerInit()
\$Pos=_ArrayBinarySearch(\$Array,35,1)
\$ABST=TimerDiff(\$Timer)

\$Timer2=TimerInit()
\$Pos2=_IntBinarySearch(\$Array,35,1,100)
\$IBST=TimerDiff(\$Timer2)
\$Out="----ABS----" & @CRLF & "POS:" & \$Pos & @CRLF & "Time:" & \$ABST & @CRLF & "----IBS----" & @CRLF & "POS:" & \$Pos2 & @CRLF & "Time:" & \$IBST
MsgBox(0,"Stats",\$Out)
ClipPut(\$Out)

Func _IntBinarySearch(ByRef \$aA, \$vE, \$iSp, \$iEp)
Local \$iP

If \$iSp < 0 Or \$iEp > UBound(\$aA) Then
\$iP = -1
Else
While \$iEp <> \$iSp And \$iP <> -1
\$iP = \$iSp + Int( (\$iEp - \$iSp) * (\$vE - \$aA[\$iSp]) / (\$aA[\$iEp] - \$aA[\$iSp]) )

If \$iP < \$iSp Or \$ip > \$iEp Then
\$iP = -1
ElseIf \$aA[\$iP] = \$vE Then
\$iEp = \$iP
\$iSp = \$iP
ElseIf \$vE < \$aA[\$iP] And \$iEp <> \$iP Then
\$iEp = \$iP
ElseIf \$aA[\$iP] < \$vE And \$iSp <> \$iP Then
\$iSp = \$iP
Else
\$iP = -1
EndIf
WEnd
EndIf

Return \$iP
EndFunc

Here are the results I got.

----ABS----

POS:35

Time:1.92510500636254

----IBS----

POS:35

Time:0.906539797655847

Thats means _IntBinarySearch() is about double the speed of _ArrayBinarySearch().

I have a suggestion though. you should give your parameters more descriptive names.

Edited by SolidSnake

HKTunes:Softpedia | GoogleCodeLyricToy:Softpedia | GoogleCodeRCTunes:Softpedia | GoogleCodeMichtaToolsProgrammer n. - An ingenious device that turns caffeine into code.

##### Share on other sites

So be it, new version. Also some bug fixing...

#include <Array.au3>
Dim \$Array[101]
\$Array[1]=100
For \$X=1 to 100
if \$x<>35 Then
\$Array[\$X]=Int(Random(0, 111))
Else
\$Array[\$X]=\$X
EndIf
Next

_ArraySort(\$Array)
\$Out=''
For \$c = 1 to 100
\$Out = \$out & \$c&'='&\$Array[\$c] & '   '
Next
\$Out = \$Out & @LF

\$Timer=TimerInit()
\$Pos=_ArrayBinarySearch(\$Array,35,1)
\$ABST=TimerDiff(\$Timer)

\$Timer2=TimerInit()
\$Pos2=_IntBinarySearch(\$Array,35,1,100)
\$IBST=TimerDiff(\$Timer2)
\$Out=\$out & "----ABS----" & @CRLF & "POS:" & \$Pos & @CRLF & "Time:" & \$ABST & @CRLF & "----IBS----" & @CRLF & "POS:" & \$Pos2 & @CRLF & "Time:" & \$IBST
MsgBox(0,"Stats",\$Out)
ClipPut(\$Out)

Func _IntBinarySearch(ByRef \$avSortedArray, \$vSeek, \$iStartingPoint, \$iEndingPoint)
Local \$iPivot

If \$iStartingPoint < 0 Or \$iEndingPoint > UBound(\$avSortedArray) Then
\$iPivot = -1
Else
While \$iEndingPoint <> \$iStartingPoint
\$iPivot = \$iStartingPoint + Round( (\$iEndingPoint - \$iStartingPoint) * (\$vSeek - \$avSortedArray[\$iStartingPoint]) / (\$avSortedArray[\$iEndingPoint] - \$avSortedArray[\$iStartingPoint]) )

If \$iPivot < \$iStartingPoint Then
\$iPivot = \$iStartingPoint
ElseIf \$iPivot > \$iEndingPoint Then
\$iPivot = \$iEndingPoint
EndIf

If \$avSortedArray[\$iPivot] = \$vSeek Then
\$iEndingPoint = \$iPivot
\$iStartingPoint = \$iPivot
ElseIf \$vSeek < \$avSortedArray[\$iPivot] And \$iEndingPoint <> \$iPivot Then
\$iEndingPoint = \$iPivot
ElseIf \$iStartingPoint <> \$iPivot Then
\$iStartingPoint = \$iPivot
Else
\$iPivot = -1
ExitLoop
EndIf
WEnd
EndIf

Return \$iPivot
EndFunc
Edited by ezzetabi

##### Share on other sites

So be it, new version. Also some bug fixing...

#include <Array.au3>
Dim \$Array[101]
\$Array[1]=100
For \$X=1 to 100
if \$x<>35 Then
\$Array[\$X]=Int(Random(0, 111))
Else
\$Array[\$X]=\$X
EndIf
Next

_ArraySort(\$Array)
\$Out=''
For \$c = 1 to 100
\$Out = \$out & \$c&'='&\$Array[\$c] & '    '
Next
\$Out = \$Out & @LF

\$Timer=TimerInit()
\$Pos=_ArrayBinarySearch(\$Array,35,1)
\$ABST=TimerDiff(\$Timer)

\$Timer2=TimerInit()
\$Pos2=_IntBinarySearch(\$Array,35,1,100)
\$IBST=TimerDiff(\$Timer2)
\$Out=\$out & "----ABS----" & @CRLF & "POS:" & \$Pos & @CRLF & "Time:" & \$ABST & @CRLF & "----IBS----" & @CRLF & "POS:" & \$Pos2 & @CRLF & "Time:" & \$IBST
MsgBox(0,"Stats",\$Out)
ClipPut(\$Out)

Func _IntBinarySearch(ByRef \$avSortedArray, \$vSeek, \$iStartingPoint, \$iEndingPoint)
Local \$iPivot

If \$iStartingPoint < 0 Or \$iEndingPoint > UBound(\$avSortedArray) Then
\$iPivot = -1
Else
While \$iEndingPoint <> \$iStartingPoint
\$iPivot = \$iStartingPoint + Round( (\$iEndingPoint - \$iStartingPoint) * (\$vSeek - \$avSortedArray[\$iStartingPoint]) / (\$avSortedArray[\$iEndingPoint] - \$avSortedArray[\$iStartingPoint]) )

If \$iPivot < \$iStartingPoint Then
\$iPivot = \$iStartingPoint
ElseIf \$iPivot > \$iEndingPoint Then
\$iPivot = \$iEndingPoint
EndIf

If \$avSortedArray[\$iPivot] = \$vSeek Then
\$iEndingPoint = \$iPivot
\$iStartingPoint = \$iPivot
ElseIf \$vSeek < \$avSortedArray[\$iPivot] And \$iEndingPoint <> \$iPivot Then
\$iEndingPoint = \$iPivot
ElseIf \$iStartingPoint <> \$iPivot Then
\$iStartingPoint = \$iPivot
Else
\$iPivot = -1
ExitLoop
EndIf
WEnd
EndIf

Return \$iPivot
EndFunc

<{POST_SNAPBACK}>

Thanks for updating your script. It should be easier for people to use now.

HKTunes:Softpedia | GoogleCodeLyricToy:Softpedia | GoogleCodeRCTunes:Softpedia | GoogleCodeMichtaToolsProgrammer n. - An ingenious device that turns caffeine into code.

##### Share on other sites

Considering the lack of answers I would say that non actually care.

## Create an account

Register a new account