Jump to content
Sign in to follow this  

Binary Search within 2D arrays

Recommended Posts



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.



Share this post

Link to post
Share on other sites

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:

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

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
            $iStart = $iMid + 1
        $iMid = Int(($iEnd + $iStart) / 2)

    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 by Authenticity

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  


Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.