Python bisecting a list

Question

I need to write a function that takes a list and bisects it (like the bisect module but I cannot use that). I normally would show what I have done so far but I really do not know how to do it without the module so I am hoping someone can help me out a bit. Here is the exact question I need to figure out:

Write a function called bisect that takes a sorted list and a target value and returns the index of the value in the list, if it’s there, or None if it’s not

Answer 1

The bisect module keeps track of a list, keeping it sorted, without having to resort every time you insert an element. The method you need to implement just needs to search inside a sorted list.

def bisect(sortedlist,targetvalue,firstindex=0,lastindex=None):

    if(len(sortedlist)==0):
        return None
    if(len(sortedlist)==1):
        if(sortedlist[0]==targetvalue):
            return firstindex
        else:
            return None
    center = int(round(len(sortedlist)/2))

    if(sortedlist[center]==targetvalue):
        return firstindex+center
    if(targetvalue>sortedlist[center]):
        return bisect(sortedlist[center+1:lastindex],targetvalue,center+1,lastindex)
    else:
        return bisect(sortedlist[0:center],targetvalue,firstindex,center-1)

this basically does a binary search. The indexes are passed to keep track of the indexes of the original list, in invocations further down the recursion loop.

Answer 2

i was doing the homework from "think python" chapter 10 exercise 8 and i tired the code above written by fred. it seems to have some bugs. 1. the counter doesn't work for long list with 100k strings 2. sometimes it returns None for things that i'm sure is in the list.

so i tweaked it a little bit:

this is my version:

it works very well, it tested it with a wordlist from swampy 2.0 named words.txt, which originally comes from the moby collection: 113809of.fic

hope this helps those of you struggling with the bisect program

def bisects (list,x,counter=0):

    if len(list)==0:
        return x,'is not in the list'
    elif(len(list)==1):
        middle = 0
    else:
        middle = int(len(list)/2)

    if x == list[middle]:
        return counter, x,'is in the list' 
    elif x < list[middle]:
        counter +=0
        return bisects(list[0:middle],x,counter)
    elif x > list[middle]:
        counter +=middle
        return bisects(list[middle+1:],x,counter) 

Also will be great if a guru can help me correct that flaw, thanks,