3 Replies - 1761 Views - Last Post: 14 March 2013 - 05:44 PM Rate Topic: -----

#1 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 24-October 12

Binary Search

Posted 13 March 2013 - 12:15 PM

Hey,
So I just learned how to do binary search and Im working on a program, but I keep getting an error, can I get some help.

def binary_search( data, key ):
    found=False
    low=0
    high=len(data)-1
    while(not found and low<=high):
        guess=(high+low)//2
        if (key==data[guess]):
            found=True
        else:
            if (key<data[guess]):
                high=guess-1
            else:
                low=guess+1
    if(not found):
        guess=-1
    return guess

def test():
    seq = []
    for i in range(1,1001):
        seq.append(i)
    for j in range(1,100):
        is_pass = (binary_search(seq,j)==j-1)
        assert is_pass == True, "fail the test when key is %d"%j
    try:
        is_pass = (binary_search(seq,-2)==0)
        assert is_pass == True, "fail the test when key is -2"
    except:
        print('Exception when key is -2')
    try:
        is_pass = (binary_search(seq,1002)==999)
        assert is_pass == True, "fail the test when key is 1002"
    except:
        print('fail the test when key is 1002')
    try:
        is_pass = (binary_search(seq,55.4)==54)
        assert is_pass == True, "fail the test when key is 55.4"
    except:
        assert False, 'fail the test when key is 55.4'
    try:
        is_pass = (binary_search(seq,55.5)==54 or binary_search(seq,55.5)==55)
        assert is_pass == True, "fail the test when key is 55.5"
    except:
        assert False, 'fail the test when key is 55.5'    
    if is_pass == True:
        print("=========== Congratulations! Your have finished exercise 1! ============")

if __name__ == '__main__':
    test() 



Heres the error:
/Desktop/WingIDE.app/Contents/MacOS/src/debug/tserver/_sandbox.py", line 49, in <module>
/Desktop/WingIDE.app/Contents/MacOS/src/debug/tserver/_sandbox.py", line 39, in test
builtins.Assertionerror: fail the test when key is 55.4

I dont know why this is happening.

Is This A Good Question/Topic? 0
  • +

Replies To: Binary Search

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2153
  • View blog
  • Posts: 3,315
  • Joined: 21-June 11

Re: Binary Search

Posted 13 March 2013 - 12:24 PM

The assertion error happens on line 39. Line 39 asserts False, so if that line is executed, you'll always get an assertion error. Since line 39 is inside an except block, this line will only be executed if the previous try block threw an exception.

So your tests fail because binary_search throws an exception. To find out why it throws an exception, you should remove the the whole exception handling code and instead just let the exception go through (or at least print the exception's message when you catch). The exception message will give you more information about what went wrong.
Was This Post Helpful? 1
  • +
  • -

#3 medaa  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 24-October 12

Re: Binary Search

Posted 13 March 2013 - 12:38 PM

I got this error:
line 40, in <module>
Syntax Error: try:: /Users/Hameda/175 Lab 8 part 1.py, line 407

The problem is for the def binary_search, because I wrote it and I was given the test to see if my prgram works
Was This Post Helpful? 0
  • +
  • -

#4 Mekire  Icon User is offline

  • D.I.C Head

Reputation: 117
  • View blog
  • Posts: 215
  • Joined: 11-January 13

Re: Binary Search

Posted 14 March 2013 - 05:44 PM

Your code passes the test just fine as long as you remove your last two lines from your function (before the return). When you fail the test looking for 55.4 the test is expecting you to find 54 or 55 instead (your teacher wants to make sure you are actually using the given search method and not just checking every number in the list). Just delete those lines and it passes.

def binary_search( data, key ):
    found=False
    low=0
    high=len(data)-1
    while(not found and low<=high):
        guess=(high+low)//2
        if (key==data[guess]):
            found=True
        else:
            if (key<data[guess]):
                high=guess-1
            else:
                low=guess+1
    return guess
=========== Congratulations! Your have finished exercise 1! ============

Seems like you had the right idea to begin with. Not sure why you added those lines.
-Mek

This post has been edited by Mekire: 14 March 2013 - 05:48 PM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1