Announcement

Collapse
No announcement yet.

Binary Search

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Binary Search

    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 )

    Code:
    #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).]
    http://www.rvalois.com.br/downloads/free/
Working...
X