_Array2D_Binary Search

[BrewManNH]

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.

expandcollapse popup

#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

[JScript]

Well, I try as much as possible not to use any UDF Arrays...

Your code is clean! I'll try, thanks.

[Norm73]

Good afternoon,
I'm looking for a solution to a search problem with the _ArrayBinarySearch() function.

There are duplicates in my array (1D or 2D).
For some reason, the output is always wrong.

Here is a variant with a function from BrewManNH.
This is my attempt to make an analogue of the _ArrayFindAll() function.

expandcollapse popup

#include <Array.au3>
Global $Array1[40], $Array2[39][2], $TLV_Array[40], $Count = 0
For $I = 0 To 39
    For $X = 1 To 6
        $Array1[$I] &= Chr(Random(65, 90, 1))
    Next
Next
For $I = 0 To 38
    $Array2[$I][0] = $Array1[$I]
    $Array2[$I][1] = ($I > 8 And $I < 19) ? 12 : $I
Next
_ArraySort($Array2,0,0,0,1)
_ArrayDisplay($Array2, "Sorted $Array2 by first column")
Local $DelDup = _Array2D_BinarySearch($Array2, 12, 1, 12)


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

Here is a variant with a function from RRRR This is my attempt to make an analogue of the _ArrayFindAll() function

expandcollapse popup

#include <Array.au3>

Local $avArray[10]

$avArray[0] = 1
$avArray[1] = 2
$avArray[2] = 2
$avArray[3] = 2
$avArray[4] = 5
$avArray[5] = 6
$avArray[6] = 4
$avArray[7] = 2
$avArray[8] = 9
$avArray[9] = 10

_ArraySort($avArray)

_ArrayDisplay($avArray, "$avArray ПОСЛЕ _ArraySort()")

$iKeyIndex = _ArrayBinaryFindAll($avArray, 2)
If Not @error Then
    _ArrayDisplay($iKeyIndex)
Else
   MsgBox(4096,'Error',' Error: ' & @error)
EndIf

Func _ArrayBinaryFindAll(Const ByRef $aArray, $vValue, $iStart = 0, $iEnd = 0, $iSubItem = 0)

    If $iStart = Default Then $iStart = 0
    If $iEnd = Default Then $iEnd = 0
    If $iSubItem = Default Then $iSubItem = 0
    $iStart = _ArrayBinarySearch($aArray, $vValue, $iStart, $iEnd, $iSubItem)
    If @error Then Return SetError(@error, 0, -1)
    Local $iIndex = 0, $avResult[UBound($aArray)] ; Set dimension for Column/Row
    Do
        $avResult[$iIndex] = $iStart
        $iIndex += 1
        $iStart = _ArrayBinarySearch($aArray, $vValue, $iStart + 1, $iEnd, $iSubItem)
    Until @error

    ReDim $avResult[$iIndex]
    Return $avResult
EndFunc   ;==>_ArrayBinaryFindAll