Sign in to follow this  
Followers 0
ezzetabi

Interpolate Binary Search

5 posts in this topic

#1 ·  Posted (edited)

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 this post


Link to post
Share on other sites



#2 ·  Posted (edited)

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 this post


Link to post
Share on other sites

#3 ·  Posted (edited)

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 this post


Link to post
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. :evil:

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

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0