Python - List Binary Search without bisect

Question

I have a list and I want to binary_search a key(number).

My code is below but I don't have a clue what to do where the bold text on code is:

(What to do with this? Is an other function? int imid = midpoint(imin, imax))

List = []
x = 1

#Import 20 numbers to list
for i in range (0,20):
    List.append (i)
print (List)

key =  input("\nGive me a number for key: ")

def midpoint(imin, imax):
    return point((imin+imax)/2)

def binary_search(List,key,imin,imax,point):
    while (imax >= imin):
        int imid = midpoint(imin, imax)

        if(List[imid] == key):
            return imid;  

        elif (List[imid] < key):
            imin = imid + 1;

        else:
            imax = imid - 1;

    return KEY_NOT_FOUND;


print (binary_search(key))

midpoint(imin, imax)
binary_search(List,key,imin,imax,point)

`int imid` is not Python code. There are no type declarations in Python. — Martijn Pieters, Dec 01 '14 at 11:59
I would suggest you to have a look at the algorithm implementation http://en.wikibooks.org/wiki/Algorithm_Implementation/Search/Binary_search#Python — aberna, Dec 01 '14 at 12:01
@Martijn Pieters Yea, it's from C#. I want to convert it to Python — ulb, Dec 01 '14 at 12:18
possible duplicate of [Binary Search in Python](http://stackoverflow.com/questions/212358/binary-search-in-python) — simonzack, Dec 01 '14 at 13:14

score 0 · Accepted Answer · answered Dec 01 '14 at 12:34

It doesn't seem to be doing anything for you; remove the call to midpoint, and point, and just have

def binary_search(List,key,imin,imax,point):
    while (imax >= imin):
        imid = (imin + imax) / 2

(However, there are some things wrong with your code, and it won't work with just that change;

You create a list called List then try to append to an uninitialized variable called myList
You 'import 20 random' numbers, but range() is not random, it's a simple sequence 1, 2, 3, 4...
range already returns a list, no need to count through it and copy it, just use it
You call binary_search with an empty List, a key, and three uninitialized variables
binary_search assumes the list is sorted, which it is, but if the comment about 'random numbers' was correct, it wouldn't be. )

Oh, yeah. You're right. I had a almost same program and i did the changes here (copy to stackoverflow and edit here) and i missed a lot like the name of the list and the comment about random numbers. Thank you, your comment was the most helpful and analyzed! — ulb, Dec 01 '14 at 13:17

Python - List Binary Search without bisect

1 Answers1