Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Programming Question (Python) - Boolean Binary Search

  1. Mar 2, 2015 #1
    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

    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.
     
    Last edited by a moderator: Mar 2, 2015
  2. jcsd
  3. Mar 2, 2015 #2

    jedishrfu

    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.
     
  4. Mar 2, 2015 #3
    how would you do that array in python guessing that middle should be just dog not a array?
     
  5. Mar 2, 2015 #4
    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
    else return "not found "
     
  6. Mar 2, 2015 #5
    wheres your iteration to loop thru the program?

    n/m "if middle is it, done. If middle is less than search term, then"
     
  7. Mar 2, 2015 #6
    thanks for the reply, still learning here :smile:
     
  8. Mar 2, 2015 #7
    I just inserted it as code so you can actually see it.
     
  9. Mar 2, 2015 #8

    jedishrfu

    Staff: Mentor

    Folks, please take some time to read PF rules!

    You cannot do someone's homework for them and post it.
     
  10. Mar 2, 2015 #9
    looks right, but not to nit pick but is there really the need for so many variables, dunno 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. :-p
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Programming Question (Python) - Boolean Binary Search
  1. Binary search help (Replies: 1)

  2. Programming in Python (Replies: 22)

  3. Binary Search Tree C++ (Replies: 1)

  4. Binary Search Error (Replies: 0)

Loading...