ARRAY.AU3 / _ArrayBinarySearch() / Bugfix

[HHS]

Hello,

I have found a "bug" in array.au3 in the function _ArrayBinarySearch().

Summary:

Not possible to get the correct index of an element when use "ß", they found always "ss".

 

Here a little Test-Script:

#include <Array.au3>

Local $Array[6] = ["a_ausser", "a_außer", "b_ausser", "b_außer", "c_ausser", "c_außer"]
_ArraySort($Array, 0, 0)
For $i=0 to UBound($Array)-1
    ConsoleWrite("Index " & $i & ": " & $Array[$i] & @CRLF)
Next

;BinarySearch
ConsoleWrite("BinarySearchIndex: " & _ArrayBinarySearch($Array, "b_außer", 0) & " <-- must be Index 3 - b_außer" & @CRLF)
ConsoleWrite("BinarySearchIndex: " & _ArrayBinarySearch($Array, "b_ausser", 0) & " <-- must be Index 2 - b_ausser" & @CRLF)

Output:

--> Press Ctrl+Alt+Break to Restart or Ctrl+Break to Stop
Index 0: a_ausser
Index 1: a_außer
Index 2: b_ausser
Index 3: b_außer
Index 4: c_ausser
Index 5: c_außer
BinarySearchIndex: 2 <-- must be Index 3 - b_außer
BinarySearchIndex: 2 <-- must be Index 2 - b_ausser
+>09:35:08 AutoIt3.exe ended.rc:0

Here is the wrong item with Index 2 found, but I search for item 3

 

now HERE my little bugfix in __ArrayBinarySearch():

expandcollapse popup

#include <Array.au3>

Local $Array[6] = ["a_ausser", "a_außer", "b_ausser", "b_außer", "c_ausser", "c_außer"]
_ArraySort($Array, 0, 0)
For $i=0 to UBound($Array)-1
    ConsoleWrite("Index " & $i & ": " & $Array[$i] & @CRLF)
Next

;BinarySearch
ConsoleWrite("BinarySearchIndex: " & __ArrayBinarySearch($Array, "b_außer", 0) & " <-- must be Index 3 - b_außer" & @CRLF)
ConsoleWrite("BinarySearchIndex: " & __ArrayBinarySearch($Array, "b_ausser", 0) & " <-- must be Index 2 - b_ausser" & @CRLF)


; #FUNCTION# ====================================================================================================================
; Author ........: Jos
; Modified.......: Ultima - added $iEnd as parameter, code cleanup; Melba23 - added support for empty & 2D arrays
; ===============================================================================================================================
Func __ArrayBinarySearch(Const ByRef $aArray, $vValue, $iStart = 0, $iEnd = 0, $iColumn = 0)
    If $iStart = Default Then $iStart = 0
    If $iEnd = Default Then $iEnd = 0
    If $iColumn = Default Then $iColumn = 0
    If Not IsArray($aArray) Then Return SetError(1, 0, -1)
    ; Bounds checking
    Local $iDim_1 = UBound($aArray, $UBOUND_ROWS)
    If $iDim_1 = 0 Then Return SetError(6, 0, -1)
    If $iEnd < 1 Or $iEnd > $iDim_1 - 1 Then $iEnd = $iDim_1 - 1
    If $iStart < 0 Then $iStart = 0
    If $iStart > $iEnd Then Return SetError(4, 0, -1)
    Local $iMid = Int(($iEnd + $iStart) / 2)
    Switch UBound($aArray, $UBOUND_DIMENSIONS)
        Case 1
            If $aArray[$iStart] > $vValue Or $aArray[$iEnd] < $vValue Then Return SetError(2, 0, -1)
            ; Search
            While $iStart <= $iMid And Not ($vValue == $Array[$iMid])
                If $vValue < $aArray[$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
        Case 2
            Local $iDim_2 = UBound($aArray, $UBOUND_COLUMNS) - 1
            If $iColumn < 0 Or $iColumn > $iDim_2 Then Return SetError(7, 0, -1)
            If $aArray[$iStart][$iColumn] > $vValue Or $aArray[$iEnd][$iColumn] < $vValue Then Return SetError(2, 0, -1)
            ; Search
            While $iStart <= $iMid And Not ($vValue == $aArray[$iMid][$iColumn])
                If $vValue < $aArray[$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
        Case Else
            Return SetError(5, 0, -1)
    EndSwitch
    Return $iMid
EndFunc   ;==>_ArrayBinarySearch

Output:

--> Press Ctrl+Alt+Break to Restart or Ctrl+Break to Stop
Index 0: a_ausser
Index 1: a_außer
Index 2: b_ausser
Index 3: b_außer
Index 4: c_ausser
Index 5: c_außer
BinarySearchIndex: 3 <-- must be Index 3 - b_außer
BinarySearchIndex: 2 <-- must be Index 2 - b_ausser
+>09:37:17 AutoIt3.exe ended.rc:0

Here is the correct item with Index 3 found.

 

Only two lines have little changes:

line 25 in function:
Original: While $iStart <= $iMid And  $vValue <> $Array[$iMid]
FIX: While $iStart <= $iMid And Not ($vValue == $Array[$iMid])
line 39 in function:
Original: While $iStart <= $iMid And $vValue <> $aArray[$iMid][$iColumn])
FIX: While $iStart <= $iMid And Not ($vValue == $aArray[$iMid][$iColumn])

 

Please check my little bugfix and check in in the repository for the next release.

Edited June 8, 2016 by HHS

[czardas]

Thanks for reporting the bug. Unfortunately your fix has an issue: this function is currently not case sensitive and therefore the change would be script breaking. Your suggestion would work with the addition of an extra case sensitivity parameter. There are probably other alternatives, but this seems to be the easiest solution to this problem. It's still not perfect.

Edited June 8, 2016 by czardas

[jchd]

I believe it all depends on which options are used by the internal call to StringCompareW. Unicode can be misleading, but German usually consider ß to be equivalent to ss.