# Python Programming Question (Python) - Boolean Binary Search

1. Mar 2, 2015

### 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:

Code (Python):

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

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.

Last edited by a moderator: Mar 2, 2015
2. Mar 2, 2015

### Staff: Mentor

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.

3. Mar 2, 2015

### thankz

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

4. Mar 2, 2015

### Fooality

Are you asking how to do that with a list, without slicing up the array into sublists? Hmmm. You could do something like

minimum = 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

5. Mar 2, 2015

### thankz

wheres your iteration to loop thru the program?

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

6. Mar 2, 2015

### thankz

thanks for the reply, still learning here

7. Mar 2, 2015

### Fooality

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

8. Mar 2, 2015