Binary Search within 2D arrays

[the123punch]

Hi,

I looked at the code for arrays and binary search only seems to work on single dimension arrays.

I am wondering, can we get a 1D-array from a 2D array?

For example I have a 2D array:

Dim $probes[2][20]

How can I get the array corresponding to the first column of my 2D arrays??

In most programming languages I know, we can do that by referring to $probes[1] or $probes[0],

but it doesn't seem to work in Autoit..

My goal would be to have a binary search on the first column of my array.

Thanks.

the123punch

[Authenticity]

To implement such a function you don't need to change the algorithm at all just to make the loops and the necessary code for 2D arrays. The array has to be sorted. I think there is an example in the Example forum that tries to implement most (if not all) of the functions in Array.au3 to support 2D arrays.

Edit: A modification to _ArrayBinarySearch(), for example:

expandcollapse popup

Local $avTest[2][8]

For $i = 0 To UBound($avTest)-1
    For $j = 0 To UBound($avTest, 2)-1
        $avTest[$i][$j] = ($i+1)*$j
    Next
Next

ConsoleWrite($avTest[1][_ArrayBinarySearch_2D($avTest, 14, 1)] & @CRLF)

; #FUNCTION# ====================================================================================================================
; Name...........: _ArrayBinarySearch
; Description ...: Uses the binary search algorithm to search through a 1-dimensional array.
; Syntax.........: _ArrayBinarySearch(Const ByRef $avArray, $vValue[, $iStart = 0[, $iEnd = 0]])
; Parameters ....: $avArray - Array to search
;                  $vValue  - Value to find
;                  $iWidth  - [optional] Index of array to start searching at
;                  $iHeight - [optional] Index of array to stop searching at
; 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 - $avArray is not a 1 dimensional array
; Author ........: Jos van der Zande <jdeb at autoitscript dot com>
; Modified.......: Ultima - added $iEnd as parameter, code cleanup
; Remarks .......: When performing a binary search on an array of items, the contents MUST be sorted before the search is done.
;                  Otherwise undefined results will be returned.
; Related .......: _ArrayFindAll, _ArraySearch
; Link ..........;
; Example .......; Yes
; ===============================================================================================================================
Func _ArrayBinarySearch_2D(Const ByRef $avArray, $vValue, $iRow, $iStart = 0, $iEnd = 0)
    If Not IsArray($avArray) Then Return SetError(1, 0, -1)
    If UBound($avArray, 0) <> 2 Or $iRow < 0 Or $iRow+1 > UBound($avArray, 2)-1 Then Return SetError(5, 0, -1)

    Local $iUBound = UBound($avArray, 2) - 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 $avArray[$iRow][$iStart] > $vValue Or $avArray[$iRow][$iEnd] < $vValue Then Return SetError(2, 0, -1)

    ; Search
    While $iStart <= $iMid And $vValue <> $avArray[$iRow][$iMid]
        If $vValue < $avArray[$iRow][$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
EndFunc   ;==>_ArrayBinarySearch_2D

Sorry Jons, if it's a little bit rude...

Edited October 21, 2009 by Authenticity