Binary Search

[Roberto Valois]

Now that you have the sorted Array using the Steve Hutchesson nrQSort,
BinSrch It!
( You can use this function to search in any sorted long/dword Array )

#Compile Exe
#Dim All
 
%NUMELEMENTS = 1000000
 
'******************************************************************************
'  BINSRCH.BAS
   
'   Binary search an array of long/dword and returns
'   1 based index If Found or %False If NOT Found.
'   I try to keep it simple for clarity. Some optimization is possible.
'   Let me know If this function works (or not).
 
'   Uses EAX,EBX,ECX,EDX,ESI
 
'******************************************************************************
 
Function BinSrch(ByVal ArrayAddr As Long, ByVal Item As Dword, ByVal NumItens As Dword) As Dword
 
  !mov esi,ArrayAddr    ' ESI = Array base addr
  !mov edx,Item         ' EDX = Item to be found
  !xor ebx,ebx          ' EBX = Low - First item
  !mov ecx,NumItens     ' ECX = High - Last Item
  !dec ecx              ' Adjust High - We are now zero based, Low = 0 and High = NumItens - 1
  AGAIN:
  !cmp ecx,ebx          ' High have to be >= Low
  !jl short NOTFOUND    ' If not get out
  !mov eax,ebx          ' Mid = Low
  !add eax,ecx          ' Mid = Low + High
  !shr eax,1            ' Mid = (Low + High) \ 2
  !cmp edx,[esi+eax*4]  ' Compare Item with (Mid)
  !jg short GT          ' Item > (Mid) ?
  !jl short LT          ' Item < (Mid) ?
  !inc eax              ' Found ! Item = (Mid). Adjust Mid to 1 based
  !jmp short FOUND      ' Happy get out
  LT:
  !mov ecx,eax          ' High = Mid
  !dec ecx              ' High = Mid - 1
  !jmp short AGAIN      ' Play it again Sam
  GT:
  !mov ebx,eax          ' Low = Mid
  !inc ebx              ' Low = Mid + 1
  !jmp short AGAIN      ' Play it again Sam
  NOTFOUND:
  !xor eax,eax          ' eax = %False
  FOUND:
  !mov Function,eax     ' Function = what is in eax
 
End Function
 
'******************************************************************************
'Test the BinSrch function
'******************************************************************************
 
Function PbMain As Long
  Register i As Dword
  Dim TstArray(1:%NUMELEMENTS) As Dword
  Dim Result As Dword
 
'Fills the TstArray with something
  For i = 1 To %NUMELEMENTS
    TstArray(i) = i
  Next i
 
'Test BinSrch.
  For i = 1 To %NUMELEMENTS
    Result = BinSrch (VarPtr(TstArray(1)),i,%NUMELEMENTS)
    If TstArray(Result) <> i Then
      MsgBox "ERROR"
      Exit Function
    End If
  Next i
  MsgBox "OK"
 
End Function

RValois

------------------


[This message has been edited by Roberto Valois (edited September 20, 2001).]