Python Programming Question (Python) - Boolean Binary Search

[NaughtyBear]

So I am in my Intro to CS course and they are going over Binary searches via an algorithm to search for simple things. The code goes as this:

Set first to 0
Set last to length-1
Set found to FALSE

WHILE (first <= last AND NOT found)
             Set middle to (first+last)/2

             IF (item equals data[middle])
                    Set found to TRUE
             ELSE
                     IF (Item < data[middle])
                           Set last to middle-1
                     ELSE
                            Set first to middle+1

Return found

This code is odd to me. Because the table next to it says many things. But the three columns of this table are First, Last, Middle and Comparison. Under these are 4 rows. In the first row it is 0, 10, 5 and cat < dog. The first table it is based off of says "Length=11" and its one column with 10 rows. In this order, (ant [0], cat [1], chicken [2], cow [3], deer [4], dog [5], fish [6], goat [7], horse [8], rat [9], snake [10]. With these, I am not understanding how the code is able to generate those search values and hope someone can understand this more than I.

 

[jedishrfu]

For a binary search algorithm to work the list you are searching must be in order.

In your example the animal names are the list you're searching and they are in alphabetical order.

So the while loop starts in the middle of the list and has three possible conditions:
1) item equals middle of the list --> we're done we found a match
2) item is less than the middle item --> next step is to search the lower half of the list
3) item is greater than the middle item --> next step is to search the upper half of the list

And of course there's the possibility that the item isn't in the list so that FOUND is false.

Laslty, I edited your post to use code tags and even though your search algorithm is in pseudo code I selected the "python" source language for it to make it easier to read.

 

[thankz]

how would you do that array in python guessing that middle should be just dog not a array?

 

[Fooality]

Are you asking how to do that with a list, without slicing up the array into sublists? Hmmm. You could do something likeminimum = 0
maximum = len(mylist)
middle = (maximum-minimum)/2
if middle is it, done. If middle is less than search term, then
minimum = middle
middle = (maximum-minimum)/2
if middle is greater than search term:
maximum = middle
middle = (maximum-minimum)/2

You loop through all this until you find it. Of course you need to put in a way to stop if not found, which I think would be of the form
if(maximum != middle)
middle = (maximum-minimum)/2
else return "not found "

 

[thankz]

wheres your iteration to loop thru the program?

n/m "if middle is it, done. If middle is less than search term, then"

 

[thankz]

thanks for the reply, still learning here

 

[Fooality]

I just inserted it as code so you can actually see it.

 

[jedishrfu]

Folks, please take some time to read PF rules!

You cannot do someone's homework for them and post it.

 

[thankz]

looks right, but not to nit pick but is there really the need for so many variables, don't know how I'd do it but I guess if you didn't know the length of the array your way is best.

I got the mit ocw lectures for python and a py2.1 bible, the last thing I did in python was learn how to use the import math header and try to put together an algo to compute pi (unsuccessfully), will get back to programming later.