Results 1 to 4 of 4

Thread: [Python] Binary search

  1. #1
    Join Date
    Feb 2009
    Posts
    2,155
    Mentioned
    4 Post(s)
    Quoted
    42 Post(s)

    Default [Python] Binary search

    I have to create a binary search algorithm through recursion.


    Code:
    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.
    Last edited by JPHamlett; 10-20-2014 at 11:23 PM.

  2. #2
    Join Date
    May 2014
    Posts
    633
    Mentioned
    8 Post(s)
    Quoted
    322 Post(s)

    Default

    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.

  3. #3
    Join Date
    Feb 2012
    Location
    Norway
    Posts
    995
    Mentioned
    145 Post(s)
    Quoted
    596 Post(s)

    Default

    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:
    python Code:
    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.
    Last edited by slacky; 11-13-2014 at 07:33 AM.
    !No priv. messages please

  4. #4
    Join Date
    Feb 2009
    Posts
    2,155
    Mentioned
    4 Post(s)
    Quoted
    42 Post(s)

    Default

    Quote Originally Posted by slacky View Post
    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:
    python Code:
    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.

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •