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 )
RValois
------------------
[This message has been edited by Roberto Valois (edited September 20, 2001).]
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
------------------
[This message has been edited by Roberto Valois (edited September 20, 2001).]