My Binary Search Algo-ma-rithm (1 Viewer)

[-X-]

Hi, since there is no way i can learn someone elses algorithm i thought i will try make my own one but It's a little different to whats in textbooks. Im just wondering if this is "acceptable" as it works when testing it.

	Begin BinarySearch (  MyArray, Value  )
        	Set lowValue to 1st index of MyArray;
            Set topValue to last index of MyArray;
	        
		WHILE ( lowValue < = topValue ) DO
			midValue = ( lowValue + topValue ) / 2;
			Select case MyArray ( midValue )
				case: = Value
					return midValue;
				case: < Value
					Set lowValue to midValue + 1;
				case: > Value
					Set topValue to midValue - 1;
			end Select;
		END WHILE
		return - 1;
	end BinarySearch ( )

Thank You.

 

[Winston]

remove the delimeters lol

i honestly dont remember psuedocode actually having a FOR LOOP control structure

the case control structure is

CASEWHERE


CASE 1


CASE 2

.
.
.
.

END CASE

 

[Glide]

You cant deviate from the normal control strucures.. and especially your brackets. Our teacher told us any hint of a programming language in your pseudocode and you will get penelised sevearly :S

 

[Glide]

yeah.. and select case is CASEWHERE and ENDCASE !!!
Dont let visual basic influence you !

 

[-X-]

Sorry just a force of habit. I realised that but i would have been pressing the backspace a million times if i wanted to get rid of it. ANyway, our teacher says it doesn't matter how you right it out as long as they can understand the logic. Writing in VB is acceptable as its almost = english. SamD can u clarify this?

edit: Im only wondering if the logic behind it is correct.

 

[Glide]

I wish it was like that... I dunno, I guess the HSC help line could provide insight, not sure :s

Im sticking to the failsafe pure pseudocode though

 

[Fosweb]

Firstly, your algorithm wont work for lists with even numbers of items.
I don't like your logic with an index that increments as the first loop. Simply using something like a Do While Not Done (Obviously not Pseudocode) and then waiting for this flag 'Done' to be true will be a better way of ending the search.
Eg: What happens if it divides the list (if it doesnt break when you try to divide a list with even amount of items in half), and your index is higher than your topValue?


Here's one I did in VB: you can just copy/paste in to run it... Add a command button to a form, leaving its name as command1

Dim myArray(100) As Integer

Private Sub Command1_Click()
search
End Sub

Sub search()
Dim lowVal%, upVal%, midVal%, searchVal%
Dim found, dead As Boolean

'fill array
For j = 0 To 99
    myArray(j) = j
    'Debug.Print j & "-" & myArray(j)
Next

searchVal = CInt(InputBox("Enter integer between 0 and 99", SearchValue))

lowVal = 0
upVal = UBound(myArray)

found = False
dead = False
While found = False And dead = False
    midVal = Int((upVal + lowVal) / 2)
    If myArray(midVal) = searchVal Then
        found = True
    Else
        Select Case myArray(midVal)
            Case Is > searchVal
                upVal = midVal
            Case Is < searchVal
                lowVal = midVal
        End Select
        If upVal = lowVal Then dead = True
    End If
Wend

If dead = False Then
    MsgBox "Found item: " & searchVal & " at array location: " & midVal
    found = False
Else
    MsgBox "It died..."
    dead = False
End If
End Sub

 

[-X-]

Originally posted by Fosweb
Firstly, your algorithm wont work for lists with even numbers of items.
I don't like your logic with an index that increments as the first loop. Simply using something like a Do While Not Done (Obviously not Pseudocode) and then waiting for this flag 'Done' to be true will be a better way of ending the search.
Eg: What happens if it divides the list (if it doesnt break when you try to divide a list with even amount of items in half), and your index is higher than your topValue?

Index has nothing to do with the topvalue? The loop returns the index when the value is found. Also, trying it with an even array and it still works. Can u please write up an array that this wont work on to test it? Cause i'm not really sure if i understand what your saying.

Thanks

 

[Fosweb]

1)	Begin BinarySearch (  MyArray, Value  )
2)        	Set lowValue to 1st index of MyArray;
3)            	Set topValue to last index of MyArray;		
4)		for ( index = 1 to topValue ) DO
5)			midValue = ( lowValue + topValue ) / 2;
6)			Select case MyArray ( midValue )
7)				case: = Value
8)					return midValue;
9)				case: < Value
10)					Set lowValue to midValue + 1;
11)				case: > Value
12)					Set topValue to midValue - 1;
13)			end Select;
14)		next index
15)		return - 1;
16)	end BinarySearch ( )

ERROR ONE:

0 1 2 3 4 5 6 7 8 9
(Searching for 2)

Desk check:

2. lowValue = 0
3. topValue = 9

4. index = 1
5. midvalue = (0 + 9) / 2 'Equals 4.5
6. case MyArray(midValue) 'ERROR. There is no array location myArray(4.5)

etc...


I cant figure out why i said that also about the other error, (index being > topValue in your FOR loop) i cant find where that would happen...
But say that you found your item on the 3rd division of a list, and say with a list of 1000 items, that would mean that index would be 3. Now say that this item was the item below the middle item in the list. You would need to increment that FOR loop, and run it another 497 times before it would close the loop (before it would reach the 'topValue'). Just an efficiency problem. Even with a list of 1000 items you wouldnt notice a problem, but if the list had 100000 items in it, you might...
You could fix this by inserting a line after line 8. index = topValue.

 

[-X-]

Error 1: Thats solved by it self since it will truncate it to 4. So if its "4.5" it would take "4".
Error 2: I cant find a way so that it would go through 500 elemnts in the array but i sort of see what u mean. If the value is not found it would have to go through all the 1000. Anyway i've edited it now, see if it works.

 

[-X-]

Originally posted by Fosweb

You could fix this by inserting a line after line 8. index = topValue.

In my previous algorithm, when i said FOR (index < = topvalue), the topValue was decrementing anyway (ie topvalue = middlevalue - 1 etc...). So it still wouldn't have gone through all the 500 elements.

 

[Inhuman]

what's "it"? You need to take the integer or truncate it manually to show the examiners you're aware of a potential error from a fractional index, you can't just assume that everything comes out alright

 

[-X-]

Originally posted by Inhuman
what's "it"? You need to take the integer or truncate it manually to show the examiners you're aware of a potential error from a fractional index, you can't just assume that everything comes out alright

As far as i know, every programming language does this, and its obvious. Even heinman textbook assumes its truncated automatically. Foswebs "midVal = Int((upVal + lowVal) / 2)" also does the samething, its assumed that it will be truncated since its an integer.

 

[Glide]

int() is a function in VB that converts the given parameter into a true integer value (that is no floating point / decimals)

I would not expect a marker to know that though D:

 

[Fosweb]

Originally posted by -X-
In my previous algorithm, when i said FOR (index < = topvalue), the topValue was decrementing anyway (ie topvalue = middlevalue - 1 etc...). So it still wouldn't have gone through all the 500 elements.

Go back and read the situation that I posted in the above post about the SPECIFIC case where this would occur!
Remember with a binary search (for a list of 1000 items), it will take a maximum of 9 (or is it 10) splits of the list to find ANY value, no matter where it is in the list.
But in the case i posted above, where that value is close to the middle value of the INITIAL list, then that topValue WILL NOT be decremented 'significantly'... Sure, it will go down by a few numbers, but you will still have a huge top value... And since the index wasnt being changed anywhere in the loop, then it would still have had to run all those extra times...

 

[enter~space~cap]

man u guys are really lucky.....

i just started year 12 and WE HAVENT EVEN LEARNT HOW TO TYPE UP WORKING PROGRAMS!!!

 

[Winston]

there's no learning of how to program in SDD, your teacher provides u with a real basic grounding knowledge and u do the rest of the research urself.