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

RomanPerekhrest · Accepted Answer · 2016-12-24 21:50:56Z

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

answered Dec 24, 2016 at 21:50

RomanPerekhrest

93.1k4 gold badges75 silver badges112 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

PTS eeker Over a year ago

İt is a homewrok so I can't do that :( I must write that algorithm by myself

fafl · Accepted Answer · 2016-12-24 21:30:20Z

0

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.

answered Dec 24, 2016 at 21:30

fafl

7,5074 gold badges32 silver badges54 bronze badges

2 Comments

PTS eeker Over a year ago

İt is a homewrok so I can't do that :(

fafl Over a year ago

Well, the additional parameters are just used internally. How else would you transport the state? Global variables?

Collectives™ on Stack Overflow

Python binary search recursive if possible

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related