Python binary search recursive if possible

Question

    class SortedList:
    theList = []


    def add(self, number):
        self.theList.append(number)
        return self.theList


    def remove(self, number):
        self.theList.remove(number)
        return self.theList


    def printList(self):
        return print(self.theList)


    def binarSearch(self, number):
        middle = (len(self.theList)//2)
        end = len(self.theList)


        if end != 0:
            if int(self.theList[middle]) == int(number):
                return print("The number is found in the list at place",middle+1)

            elif int(self.theList[middle]) < int(number):
                self.theList = self.theList[middle:]
                return self.binarSearch(number)

            elif int(self.theList[middle]) > int(number):
                self.theList = self.theList[:middle]
                return self.binarSearch(number)



        else:
            return print("The list is empty")

sorted = SortedList() #create a SortedList object

sorted.add("1")
sorted.add("2")
sorted.add("3")
sorted.add("4")
sorted.add("5")
sorted.add("6")

sorted.printList()
sorted.binarSearch(3)

I cannot use additional parameters I mut use only self and number. I want to make it recursive but if it is hard you can answer as normal. This code works good until the number 4. When I give 4 for searching it says it is in place 2 and it continues saying two after 4. I have tried adding other numbers but it is same

Answer 1

Just a hint: You can use additional parameters if you give them default values. Your method signature would look like this:

def binarSearch(self, number, start=0, end=len(self.theList)):

So it could still be called like sorted.binarySearch(5) but would internally be able to pass the state correctly.

Answer 2

Python already has a great module bisect which performs a binary search for sorted lists:

import bisect

l = [2,3,1,5,6,7,9,8,4]

print(bisect.bisect(l, 4))   # Output: 3

Familiarize yourself with this library:

https://docs.python.org/3.5/library/bisect.html