Interpolate Binary Search

[ezzetabi]

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 July 19, 2005 by ezzetabi

[FuryCell]

Cool. Look at this example.

expandcollapse popup

#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 July 19, 2005 by SolidSnake

[ezzetabi]

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 July 19, 2005 by ezzetabi

[FuryCell]

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.

[ezzetabi]

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