Write a recursive binary search function for an array. 1

[Transcend]

Hi there

Can anyone help me with writing a recursive binary search function for an array.

For example i have an array populated with integers that is already sorted. I want to write a find() function that will take a number as well as the array and return the true if the integer is in the array and false if it isn't.

Transcend

 

[fredericofonseca]

Function EntityType(EntityId As String, alldescriptions as variant) As String
On Error GoTo ErrorHandler
' perform a binary search to identify if a particular string is in the loaded objects list
' if one is found go back until the very first occurrence if found
Dim min As Long
Dim max As Long
Dim middle As Long
Dim sstring As String
Dim sEntityType As String
Dim bFound As Boolean
bFound = False
min = 0
sEntityType = ""

max = UBound(alldescriptions, 2)
While Not bFound And Not (min > max)
middle = (max + min) / 2
sstring = alldescriptions(0, middle)
If sstring > EntityId Then
max = middle - 1
Else
If sstring < EntityId Then
min = middle + 1
Else
If sstring = EntityId Then
bFound = True
sEntityType = CheckNull(alldescriptions(2, middle))
End If
End If
End If
Wend
EntityType = sEntityType

Finish:
Exit Function
ErrorHandler:
Call ErrorRoutine(&quot;ListDependents::EntityType&quot
End Function



Regards

Frederico Fonseca
SysSoft Integrated Ltd

http://www.syssoft-int.com

 

[MichaelRed]

It is not a recursive routine. While the requirement is -pwehaps- indicative of a student / homework assignment (why else would one REQUIRE a function to be recirsive?), I would think it useful to at least mention this.

The routine is set up to return a string, not the integer which -again- is a requirement.

The routine invcludes references (calls) to 'user defined functions' (CheckNull, ErrorRoutine) which are not included and their purpose is not explained.


These 'oddities' may represent either an incomplete response or (since MY suspicion is that is a student/ homework assignment) a clever mis-direction technique to keep the students from posting in this forum.



MichaelRed
m.red@att.net

Searching for employment in all the wrong places

 

[fredericofonseca]

Michael,

Very good comments.

And to make thinks completely clear

This does smell like homework, although the history of Transcend makes me think it may not be.

This code has everything that is needed to create a recursive function as the main body has the binary search bit which is the worst one to do.

Passing this to a recursive is easy if you know what a recursive function is (if you don't then search google!!).

The callable functions names should make it clear that they are not required for the search.



Regards

Frederico Fonseca
SysSoft Integrated Ltd

http://www.syssoft-int.com

 

[vb5prgrmr]

Ok, I could be wrong about this but when I first read this post I was wondering why recursive and why binary when you could just use a for loop from lbound to ubound. Then it hit me.... speed is the factor here. I think the words binary search are being misinterpreted here or I could just be misinterpreting the replies themselves, but I think Transcend is wanting a function that does the following...

'Say you have an array
[tt]
Dim MyArray(50) As Integer, I As Integer
[/tt]
'and it is filled with values in order from 0 to 50
[tt]
For I = 0 To 50
MyArray(I) = I
Next I
[/tt]
and you want to find if the value of 20 is in the array. So my understanding of a binary search pattern is...

On the first call you take UBound - LBound / 2 (=25)
you then check the array index number 25 (and in this case it is 25) which is greater than 20

So second call would be 25 / 2 (=12)
Which is less than 20

Third call difference between 12 and 25 plus 12 (=18)
Less than 20

4th call difference between 18 and 25 + 18 (=22) > 20

5th call difference between 18 and 22 + 18 (20) = 20 returns true

Thus making this function faster than a for loop especially if the contentents of the array are not consecutive (0 to 50) and if the array contains a wide value set, and once the function is done correctly it would be easy to code...
[tt]
If SomeFunction(MyArray, MyValue) = True Then
Else
End If
[/tt]

Then again I could be out in left field watching as the ball sails over my head!!!

 

[Transcend]

Well this isn't homework .. I finished my university degree at the end of 2000 but i guess I can see why you thought it may be so.

I probably should have been more clear, I guess it doesn't matter necessarily that the function be recursive - as long as it works.

To provide some background I actually was looking at some functions in the .net framework and saw that there is an array.binarysearch function in the framework and wondered if i could implement something like it in my vb 6 applications.

Vbprgrmr is on the right track with what i want. A binary search has a speed of log2N where N is the number of array elements. This method is must faster than looping through all the array elements! The basics of it are that you are searching for an element ie 20. You find the middle element of your array and find whether or not it is higher or lower that that one. If its higher you search the end half of the array etc etc. The array of course has to be sorted before you can implement a binary search on it else it won't work at all! Thanks all for your ideas.

fredericofonseca's method does pretty much exactly what I had in mind just there is a loop in it rather than being recursive, but thanks for that

I will post the function i come up with tomorrow!

Thanks again


Transcend

 

[Transcend]

Oh and just to add

&quot;This code has everything that is needed to create a recursive function as the main body has the binary search bit which is the worst one to do&quot;

This is so true, with what you posted fredericofonseca I can figure out the rest myself!

Was a little sleepy when I posted the last message so i went on a bit ...

Thanks for your help

Transcend

 

[fredericofonseca]

Transcend,

I did place the code based on your background here. Otherwise I would not even given you that.

There is no need to create a recursive function for this unless you can prove it to be faster.

Remember that you have the overhead of calling the function, reallocating local variables needed (if any).

I use this particular function on a rather big array (150.000 to 200.000 (times 4 items per record) records) just to get the description of an entity given it's name, and because of memory issues I don't even pass the array to the function, and instead it is declared as global.

Being recursive seemed slower on my case.





Regards

Frederico Fonseca
SysSoft Integrated Ltd

http://www.syssoft-int.com

 

[CajunCenturion]

Could it be we're confusing a binary search with a binary tree?

There is no way that a recursive function to search a sorted array would be faster, plus, an array is not the type of heirarchical structure that lends itself to recursive processes.

To search a sorted array - use a binary search.
To search a binary tree - use a recursive function.

Good Luck
--------------
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[fredericofonseca]

According to the OP he has
1- Sorted Array of integers
2- Requires to find if a particular integer is part of the array.

This and adding to his answers leads me to believe that he wishs to have a BINARY SEARCH of an array, not a search of a binary tree.




Regards

Frederico Fonseca
SysSoft Integrated Ltd

http://www.syssoft-int.com

 

[MichaelRed]

on the other hand, the binary search requires the set to be (pre) sorted. If -at any point in the process- it is necessary to do the sorting, and it is not ancillary to other requirements, then the simple loop is quite likely to be faster than the sort + the binary search.





MichaelRed
m.red@att.net

Searching for employment in all the wrong places

 

[Transcend]

In my case (thats *she* ) the array is already sorted and fredericofonseca is right i want to do a binary search of a sorted array not a search of a binary tree. Thnking about the overhead you are probably right in that making it recursive will not necessarily make it faster. I am going to write it up today and see how it goes.

Transcend

 

[Transcend]

Ok well I've got what I needed.

I ended up getting it to work in .net too just for fun and ended up with

Private Function Find(ByVal INTARR() As Integer, ByVal intFind As Integer) As Integer
Dim blnFound As Boolean
Dim min As Integer
Dim max As Integer
Dim middle As Integer
Dim returnint As Integer

max = INTARR.GetUpperBound(0)

blnFound = False
While Not blnFound And Not (min > max)
middle = (max + min) / 2
returnint = INTARR(middle)
If returnint > intFind Then
max = middle - 1
Else
If returnint < intFind Then
min = middle + 1
Else
If returnint = intFind Then
blnFound = True
Return middle
End If
End If
End If
End While
Return returnint
End Function

Thanks to fredericofonseca your code was a great help. In this instance i return the array index where the integer was found. If the integer is not found then the index that gets returned is the array.upperbound + 1.

Many thanks

Transcend

 

[fredericofonseca]

Now that I know your'r a &quot;she&quot; I won't make that mistake again.

As for your code I have two comments.
1- Do not use the name &quot;find&quot; as a function name.
Always use names that can not be confused by the language keywords.

2- you said &quot; If the integer is not found then the index that gets returned is the array.upperbound + 1&quot;.
this is incorrect. In order for this to be true you would need the following.

        max = INTARR.GetUpperBound(0)
        realmax = max

        blnFound = False
        While Not blnFound And Not (min > max)
(snip) ... 
        End While

 '       Return returnint (replace with
        return (realmax + 1)



Regards

Frederico Fonseca
SysSoft Integrated Ltd
[URL unfurl="true"]www.syssoft-int.com[/URL]

 

[Transcend]

Ah yes you are right I was wrong about that getting returned. And thanks for the pointer

Transcend