Sign in to follow this  
Followers 0
BrewManNH

_Array2D_Binary Search

2 posts in this topic

I encountered the speed of using _ArrayBinarySearch while working on a project of mine. I had previously been using _ArraySearch in the project to find duplicate items in 2 different arrays so that I could add the contents of the second array to the first one without having any duplicates. Unfortunately, the arrays I was searching had over 4000 rows in each, and using _ArraySearch to search through this took about 30-60 seconds on average on my older laptop. I had been using _ArraySearch because _ArrayBinarySearch only worked on 1D arrays and one of my arrays was 2D. My workaround for this was to create a temporary array that only contained the column of the 2D array I actually needed to search through, sorted it, and then used _ArrayBinarySearch to do my search for duplicates. This took the search time down to well under 1 second on average to go through the 2 arrays.

So, you're probably wondering why I'm mentioning this. Well, the reason I had to go through the array gymnastics was because of the 1D array limitations of _ArrayBinarySearch. I figured that I would look at the function and see if I could tweak it to use search a sorted 2D array, and that's exactly what I've done. The function below has the same caveats as the original search function, the column that you're searching on MUST be sorted or you will end up with undefined results. It's actually very simple to use this function and it can be used in place of _ArrayBinarySearch because it will search both 1D and 2D arrays using the same code as the original function did, I just modified it to work with 2 dimensional arrays.

Here's the code and a quickly thrown together example of how I used it to search 2 arrays for duplicate items.

#include <Array.au3>
Global $Array1[4000], $Array2[3999][2], $TLV_Array[4000], $Count = 0
For $I = 0 To 3999
    For $X = 1 To 30
        $Array1[$I] &= Chr(Random(65, 90, 1))
    Next
Next
For $I = 0 To 3998
    $Array2[$I][0] = $Array1[$I]
    $Array2[$I][1] = $I
Next
_ArraySort($Array2)
_ArrayDisplay($Array2, "Sorted $Array2 by first column")
$Timer = TimerInit()
For $I = UBound($Array1) - 1 To 0 Step -1
    Local $Read1 = $Array1[$I]
    Local $DelDup = _Array2D_BinarySearch($Array2, $Read1, 0)
    If $DelDup = -1 Then
        $TLV_Array[$Count] = $Array1[$I]
        $Count += 1
    EndIf
Next
ReDim $TLV_Array[$Count]
$Array1 = $TLV_Array
ConsoleWrite("@@ (" & @ScriptLineNumber & ") :  Time to check for duplicate files: " & Int(TimerDiff($Timer)) / 1000 & @CRLF)
_ArrayDisplay($Array1, "$Array1 after deleting the duplicates")


; #FUNCTION# ====================================================================================================================
; Name...........: _Array2D_BinarySearch
; Description ...: Uses the binary search algorithm to search through a 1 or 2-dimensional array.
; Syntax.........: _Array2D_BinarySearch(Const ByRef $avArray, $vValue[, $iColumn = 0[, $iStart = 0[, $iEnd = 0]]])
; Parameters ....: $avArray - Array to search
;                  $vValue  - Value to find
;                  $iColumn - [optional] Which column to search on [Default = First (0) column]
;                  $iStart  - [optional] Index of array to start searching at [Default = start of array]
;                  $iEnd    - [optional] Index of array to stop searching at [Default = end of array]
; Return values .: Success - Index that value was found at
;                  Failure - -1, sets @error to:
;                  |1 - $avArray is not an array
;                  |2 - $vValue outside of array's min/max values
;                  |3 - $vValue was not found in array
;                  |4 - $iStart is greater than $iEnd
;                  |5 - $iColumn is greater than actual number of columns
;                  |6 - $avArray has too many dimensions
; Author ........: Jos van der Zande <jdeb at autoitscript dot com>
; Modified.......: Ultima - added $iEnd as parameter, code cleanup
; Modified.......: BrewManNH - added ability to search a 2D array
; Remarks .......: When performing a binary search on an array of items, the contents of the column being searched MUST be
;                  sorted before the search is done, otherwise undefined results will be returned.
; Related .......: _ArrayFindAll, _ArraySearch, _ArrayBinarySearch
; Link ..........:
; Example .......: Yes
; ===============================================================================================================================
Func _Array2D_BinarySearch(Const ByRef $avArray, $vValue, $iColumn = 0, $iStart = 0, $iEnd = 0)
    If UBound($avArray, 0) > 2 Then Return SetError(6, 0, -1)
    Local $i2D = False
    If UBound($avArray, 0) > 1 Then
        $i2D = True
    EndIf
    If UBound($avArray, 2) < $iColumn Then Return SetError(5, 0, -1)
    If Not IsArray($avArray) Then Return SetError(1, 0, -1)
    Local $iUBound = UBound($avArray) - 1
    ; Bounds checking
    If $iEnd < 1 Or $iEnd > $iUBound Then $iEnd = $iUBound
    If $iStart < 0 Then $iStart = 0
    If $iStart > $iEnd Then Return SetError(4, 0, -1)
    Local $iMid = Int(($iEnd + $iStart) / 2)
    If Not $i2D Then
        If $avArray[$iStart] > $vValue Or $avArray[$iEnd] < $vValue Then Return SetError(2, 0, -1)
        ; Search
        While $iStart <= $iMid And $vValue <> $avArray[$iMid]
            If $vValue < $avArray[$iMid] Then
                $iEnd = $iMid - 1
            Else
                $iStart = $iMid + 1
            EndIf
            $iMid = Int(($iEnd + $iStart) / 2)
        WEnd
        If $iStart > $iEnd Then Return SetError(3, 0, -1) ; Entry not found
        Return $iMid
    Else
        If $avArray[$iStart][$iColumn] > $vValue Or $avArray[$iEnd][$iColumn] < $vValue Then Return SetError(2, 0, -1)
        ; Search
        While $iStart <= $iMid And $vValue <> $avArray[$iMid][$iColumn]
            If $vValue < $avArray[$iMid][$iColumn] Then
                $iEnd = $iMid - 1
            Else
                $iStart = $iMid + 1
            EndIf
            $iMid = Int(($iEnd + $iStart) / 2)
        WEnd
        If $iStart > $iEnd Then Return SetError(3, 0, -1) ; Entry not found
        Return $iMid
    EndIf
EndFunc   ;==>_Array2D_BinarySearch

If I posted any code, assume that code was written using the latest release version unless stated otherwise. Also, if it doesn't work on XP I can't help with that because I don't have access to XP, and I'm not going to.
Give a programmer the correct code and he can do his work for a day. Teach a programmer to debug and he can do his work for a lifetime - by Chirag Gude
How to ask questions the smart way!

I hereby grant any person the right to use any code I post, that I am the original author of, on the autoitscript.com forums, unless I've specifically stated otherwise in the code or the thread post. If you do use my code all I ask, as a courtesy, is to make note of where you got it from.

Back up and restore Windows user files _Array.au3 - Modified array functions that include support for 2D arrays.  -  ColorChooser - An add-on for SciTE that pops up a color dialog so you can select and paste a color code into a script.  -  Customizable Splashscreen GUI w/Progress Bar - Create a custom "splash screen" GUI with a progress bar and custom label.  -  _FileGetProperty - Retrieve the properties of a file  -  SciTE Toolbar - A toolbar demo for use with the SciTE editor  -  GUIRegisterMsg demo - Demo script to show how to use the Windows messages to interact with controls and your GUI.  -   Latin Square password generator

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