Binary Searching and lists

Question

class BinaryStringList():
    def __init_(self):
        self.item = []

    def strAdd(self,item):
        self.items.append(item)

    def finditem(self, item):

        if len(self)==0:
            print("List is empty!")
        else:
            midpoint = len(self)//2
            if self[midpoint]==item:
                print("Item Found ", item)
            else:
                if item<self[midpoint]:
                    return finditem(self[:midpoint], item)
                else:
                    return finditem(self[midpoint+1:], item)

So where I am finding I have an issue is when trying to add items to the list. If i do something like:

alist = BinaryStringList()
alist.strAdd("test1")

my code fails stating object has no attribute. Not sure why it is failing since I have almost the exact same code for another program except the find is using a sequential search where as this is a binary search.

class SequentialStringList(): def __init__(self): self.items = [] def strAdd(self, item): self.items.append(item) def findItem(self, item): for string in self.items: if string == item: return string return 'None' def iadd(): alist = SequentialStringList() for x in range(20): alist.strAdd("test"+str(x)) print(alist.findItem("test19")) works fine. — Mark Bruner, Feb 17 '17 at 00:57
Side-note: If this is for a class, then whatever, but if you're trying to do this for real code, I should note that [the `bisect` module](https://docs.python.org/3/library/bisect.html) is _the_ correct way to do binary search in Python. — ShadowRanger, Feb 17 '17 at 00:57
@MarkBruner: If you need to add/update code, edit the question, don't put it in a comment. You can't format or even line break comments. — ShadowRanger, Feb 17 '17 at 00:58
This is for a class and not sure why my code in the comment isnt working but I have basically the same add function for a sequential search and it works fine. Not sure if that's sheer luck or not. The error Im getting with the binary search is the object BinaryStringList has no object "item". — Mark Bruner, Feb 17 '17 at 01:01

score 0 · Answer 1 · answered Feb 17 '17 at 01:04

Your code is failing because you misspelled __init__. You need two underscores on each side, or it's just a weirdly named method. Since you lack a __init__, the default __init__ (which sets no attributes) is used, and you don't have an item or items attribute. You need to fix the __init__, and use a consistent name for items:

class BinaryStringList():
    def __init__(self):  # <-- Added extra trailing underscore
        self.items = []  # Fixed name to be items, not item

You have many other problems here (you're not maintaining sorted order, so binary search won't work, you haven't implemented __getitem__ so self[midpoint] won't work so you'd need self.items[midpoint], lack of __len__ means len(self) won't work either, etc.), but the two issues above are what specifically makes you get the AttributeError.

Thank you didn't see the missing underscore. I am sure I have many issues I just needed help getting past this first one in order to progress. — Mark Bruner, Feb 17 '17 at 01:12

score 0 · Accepted Answer · answered Feb 17 '17 at 01:21

You have multiple syntax errors in your code. Also recursion doesn't work that way, you need to have a base condition which returns. This solution will work, but I strongly suggest you to solve simpler problems using recursion to understand how it works.

class BinaryStringList:
    def __init__(self): # You had 1 _ after init
        self.items = [] # Typo, should have been items.

    def strAdd(self,item):
        self.items.append(item)

    def finditem(self, item):
        return self.binser(self.items, item)

    def binser(self, items, item):
        if len(items)==0:
            return

        midpoint = len(items)/2 # len(self) means nothing, it should be len(self.items)
        if items[midpoint]==item:
            return item
        else:
            if item<items[midpoint]:
                return self.binser(items[:midpoint], item) #self[:midpoint] means nothing, you needed self.items[:midpoint]
            else:
                return self.binser(items[midpoint+1:], item)

binser = BinaryStringList()
binser.strAdd(1) # You added a string here. Your logic won't work with string.
binser.strAdd(2)
binser.strAdd(3)
binser.strAdd(5)
binser.strAdd(8)
binser.strAdd(9)
binser.strAdd(10)

print binser.finditem(1)
print binser.finditem(10)
print binser.finditem(5)
print binser.finditem(11)

(there are other ways of solving binary search too - i.e. iterative approach, passing low/high index values rather than splicing the input array). Try to solve binary search using those two approaches.

Binary search with passing low/high index values, your signature for binser will look like: def binser(self, low, high, item):

So you saw what I was attempting to do. I was going for the recursion approach due to having to benchmark the assignment. Though I may look at the other approaches to benchmark as well. If you have a link that I could read up on the low/high index that would be great. — Mark Bruner, Feb 17 '17 at 01:34
Would those still be relevant for handling strings over and int? for purpose of testing im just doing a for loop to add an int to the string "test" and add those to the array. — Mark Bruner, Feb 17 '17 at 01:45
Binary search compares values and checks which is greater/lesser. So if you use "test1", "test2" etc, your code needs to determine `test1 < test2`. Probably by stripping out "test" and comparing ints. https://en.wikipedia.org/wiki/Binary_search_algorithm I don't see any reason to use string. Simply use ints. Please accept the answer if it answers your question. — zengr, Feb 17 '17 at 05:44

Binary Searching and lists

2 Answers2