SRL Archive - Python/Perl Help and Tutorials

I have to create a binary search algorithm through recursion.

theList = ['boa','cat','dog','eel','fish','gerbil','hamster','pig','tarantula']

def bSearch(lst, key, index, leng):
    print("//////////////////////////")
    index = int(index)
    leng = int(leng)
    print("Comparing ", lst[index], " and ", key)
    print("Index ", index, " Length " , leng)
    if lst[index] == key:
        return index
    if index == 0 or index == 8:
        return -1
    print("Is lst[index] > key?: ", lst[index]  > key)
    if (lst[index]  > key):
        print("Decrease Index " , leng/2, " leng " , leng/2)
        return bSearch(lst, key, index - leng/2, leng - leng/2)
    print("Increase index ", leng/2, " leng " , leng/2)
    return bSearch(lst, key, index  + leng/2, leng  - leng/2)

It can find every key except for tarantula. If I search for it I is an infinite loop?

I can figure out where my logic fails but not how to solve it…

At the end I keep adding 0 to both of the parameters.

I'm not sure if you still need help with this; however, I think the issue causing weird behavior when I try to run this is you check whether index == 0 and index == 8. Changing them to index < 0 and index > 8 seems to do the trick for me when I run this.

Perhaps also add a check to terminate if length is 0 if the previous suggestion doesn't do anything.

This is a tad longer then yours (on the other hand this one works), I've added some checks for it not to error if EG the list is empty, also you do not have to pass the length and such by param, so it's simpler to use:

def bsearch(lst, value, left=0, right=None):
  if not(lst): return None                   #empty list? return None
  if right is None: right=len(lst)-1         #set right if it's not given
  
  if left == right:                          #fail unless this is the given `value`
    if lst[left] == value: return left
    else: return None
  
  mid = (left+right) >> 1                    #(left+right) // 2
  if lst[mid] > value:                       
    return bsearch(lst, value, left, mid-1)  #recurse lower part
  elif lst[mid] < value:                     
    return bsearch(lst, value, mid+1, right) #recurse upper part
  else: 
    return mid                               #must be the given `value`

data = ['boa','cat','dog','eel','fish','gerbil','hamster','pig','tarantula']
print bsearch(data,'tarantula');

Now I personally prefer a iterative method, as it has less overhead and is simpler to write, and understand.

From: slacky
This is a tad longer then yours (on the other hand this one works), I've added some checks for it not to error if EG the list is empty, also you do not have to pass the length and such by param, so it's simpler to use:

def bsearch(lst, value, left=0, right=None):
  if not(lst): return None                   #empty list? return None
  if right is None: right=len(lst)-1         #set right if it's not given
  
  if left == right:                          #fail unless this is the given `value`
    if lst[left] == value: return left
    else: return None
  
  mid = (left+right) >> 1                    #(left+right) // 2
  if lst[mid] > value:                       
    return bsearch(lst, value, left, mid-1)  #recurse lower part
  elif lst[mid] < value:                     
    return bsearch(lst, value, mid+1, right) #recurse upper part
  else: 
    return mid                               #must be the given `value`

data = ['boa','cat','dog','eel','fish','gerbil','hamster','pig','tarantula']
print bsearch(data,'tarantula');

Now I personally prefer a iterative method, as it has less overhead and is simpler to write, and understand.

I wanted to write a method that is simpler however we have certain stupid constraints put on us in classs.