1,105,417 Community Members

Binary search

JesW9
Newbie Poster
1 post since Mar 2013
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
Unverified Member
 
0
 
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() 

I want it to do this:
If there doesn't exist, return with the index of the number whose value is closest to the object value. If
two or more found, just pick one of your choice.

I keep getting an error, can I get some help?

Member Avatar
Lardmeister
Posting Virtuoso
1,966 posts since Mar 2007
Reputation Points: 434 [?]
Q&As Helped to Solve: 111 [?]
Skill Endorsements: 8 [?]
 
1
 

Python module bisect will make your life easier.
Also remember that you have to search on a sorted sequence.

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article