_ArrayBinarySearchNear() when no match

[pixelsearch]

Hi all
The purpose of this script is, when a match isn't found during the function _ArrayBinarySearch(), to be able to access the nearest value (and index) just below the value searched, even when no match has been done. Then the user can use it or not.

Actually this can't be done with AutoIt (I think) and it's useful, especially in 2D arrays using ranges (from... to), so you can "grab" the value of a column in the nearest index row below, in case it's useful for your app.

You will recognize at the end of the script an amended version of the function _ArrayBinarySearch() extracted from Array.au3 . This function has been created/modified by Jos/Ultima/Melba23 and now I tweaked 2 lines into it, then renamed this new function _ArrayBinarySearchNear()

Here are the changes made to the lines. Original line :
If $iStart > $iEnd Then Return SetError(3, 0, -1) ; Entry not found

Tweaked line :
If $iStart > $iEnd Then Return SetError(3, $iMid, -1) ; Entry not found (@error = 3) ...but @extended now contains the nearest index below

As you see, @extended is used to return the nearest index below the "non-found" value. As @extended isn't used at all by the function, then it shouldn't be script-breaking. Also the speed of the function remains exactly the same, which is crucial in this function.

Here are the displays shown by the script below. Let's imagine we're searching the value 20, within a sorted array (the array must be sorted when using binary search)

Example with 1D array :

Example with 2D array, search in column 0

Example with 2D array, search in column 1, results are very different (gladly this is normal)

If you try the script, please modify some values in it (the value to search, the column if 2D, use the 1D or 2D arrays found in the script, alternately etc...). My tests went well but the more tests are done, the better it is.

Please report if you find something that's not correct.
Thanks for reading

expandcollapse popup

#include <Array.au3>
#include <MsgBoxConstants.au3>

Local $aArray[10] = [5, 10, 17, 25, 55, 70, 90, 95, 99, 500]

; Local $aArray[10][2] = [[5, 1.3], [10, 3.5], [17, 4.4], [25, 9.8], [55, 11.5], [70, 12.6], [90, 30.5], [95, 35.5], [99, 37.9], [500, 42.5]]

Local $vValue = 20, $iStart = 0, $iEnd = 0, $iColumn = 0

; ========== SORT LINES ==========
; 0=ascending, 0=start sorting on 1st element (1D) or row (2D), 0=stop sorting on last element or row
Local $iSortSucceed = _ArraySort($aArray, 0, 0, 0, $iColumn)
Local $iSortError = @error
If $iSortSucceed = 0 Then
    MsgBox($MB_TOPMOST, "Unsuccessful Sort", _
      "@error = " & $iSortError & "  (please consult help file, topic _ArraySort)")
    Exit
EndIf
_ArrayDisplay($aArray, "After sort" & ((UBound($aArray, $UBOUND_DIMENSIONS) = 1) ? ("") : (" on Col. " & $iColumn)))
; ================================

Local $iIndex = _ArrayBinarySearchNear($aArray, $vValue, $iStart, $iEnd, $iColumn)
Local $iError = @error, $iExtended = @extended

If $iIndex >= 0 Then
    MsgBox($MB_TOPMOST, "$vValue " & $vValue & " found" , "index = " & $iIndex)
    Exit
EndIf

Local $sError_Msg = ""
Switch $iError
    Case 1
        $sError_Msg = "$aArray is not an array"

    Case 2
        $sError_Msg = "$vValue outside of array min/max values"

    Case 3  ; $vValue was not found in array
        Switch UBound($aArray, $UBOUND_DIMENSIONS) ; 1 or 2
            Case 1
                $sError_Msg = "$vValue " & $vValue & " not found but..." & @CRLF & @CRLF & _
                  "=> nearest value below = " & $aArray[$iExtended] & @CRLF & _
                  "=> nearest index below = " & $iExtended

            Case 2
                $sError_Msg = "$vValue " & $vValue & " not found in column " & $iColumn & " but..." & @CRLF & @CRLF & _
                  "=> nearest value below = " & $aArray[$iExtended][$iColumn] & @CRLF & _
                  "=> nearest index below = " & $iExtended

            Case Else
                $sError_Msg = "$UBOUND_DIMENSIONS = " & UBound($aArray, $UBOUND_DIMENSIONS) & " (impossible)"
        EndSwitch

    Case 4
        $sError_Msg = "$iStart is greater than $iEnd"

    Case 5
        $sError_Msg = "$aArray is not a 1D or 2D array"

    Case 6
        $sError_Msg = "$aArray is empty"

    Case 7
        $sError_Msg = "$iColumn outside array bounds"

    Case Else
        $sError_Msg = "This error number is unknown"
EndSwitch

MsgBox($MB_TOPMOST, "_ArrayBinarySearchNear : @error = " & $iError, $sError_Msg)


; #FUNCTION# ================================================================================================================
; Author ........: Jos
; Modified.......: Ultima - added $iEnd as parameter, code cleanup; Melba23 - added support for empty & 2D arrays
; Modified.......: Pixelsearch - when no match, return the nearest index below into @extended (not script-breaking, 2 lines tweaked)
; ==========================================================================================================
Func _ArrayBinarySearchNear(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 $vValue <> $aArray[$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
            If $iStart > $iEnd Then Return SetError(3, $iMid, -1) ; Entry not found (@error = 3) ...but @extended now contains the nearest index below
        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 $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
            If $iStart > $iEnd Then Return SetError(3, $iMid, -1) ; Entry not found (@error = 3) ...but @extended now contains the nearest index below
        Case Else
            Return SetError(5, 0, -1)
    EndSwitch

    Return $iMid
EndFunc   ;==>_ArrayBinarySearchNear

 

[Skeletor]

I couldn't help but notice you are still using Windows XP.. hope this is a VM you got and not your host.