# Binary Search within 2D arrays

## Recommended Posts

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

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

## Create an account

Register a new account