1.11M Members

Binary search

 
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?

 
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 six months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article