How to find sequence split in list using recursion in Python

Question

I need to complete this code for school.
The program should find an index of sequence split in the list. For example for input which is a list like this

[66, 81, 83, 96, 13, 19, 30, 41, 44, 57]

the correct output should be 4 (index of number where the sequence is interrupted - 96)

My function is able to find the split but I don't know how to return an index of that split. It always return incorrect answer.

Here is my code:

def findSplit( list ):

    if len(list)%2 == 0:
        if list[(len(list)//2)-1] == list[0]:
            return 1

        elif list[(len(list)//2)-1]<list[0]:
            return  findSplit(list[:(len(list)//2)]) - len(list)//2

        elif list[(len(list)//2)-1]>list[0]:
            return findSplit(list[(len(list)//2)-1:]) + len(list)//2

    elif len(list)%2 != 0:
        if list[(len(list)//2)]<list[0]:

            return  findSplit(list[:(len(list)//2)+1]) - len(list)//2

        elif list[(len(list)//2)]>list[0]:

            return findSplit(list[(len(list)//2):]) + len(list)//2  

if __name__ == "__main__":

    list = [ 66, 81, 83, 96, 13, 19, 30, 41, 44, 57 ]

    line = input().strip().split()
    if line != []:
        list = []
        for x in line:
            list.append( int( x ) )

    print(findSplit( list ))

Bhargav Rao · Accepted Answer · 2015-12-20 19:46:20Z

1

First and most importantly don't name any of your variables list as they overwrite the builtin function. I have changed the name to lst in my code below.

Your code is fine except for a small mistake, when ever you find out that the split is the first half, you need not subtract the length of the other half.

return findSplit(lst[:(len(list)//2)+1])  # THIS MUCH IS ENOUGH!

This is because you are returning the index in the first half, hence the indices start from this half itself. If you subtract you are going into the negative. In your particular case, you are subtracting 4 (the correct value) with 5 (the length of the other split) and hence you are getting the wrong answer -1 which is 4-5.

The edited code can be written as

def findSplit( lst ):
    if len(lst)%2 == 0:
        if lst[(len(lst)//2)-1] == lst[0]:
            return 1    
        elif lst[(len(lst)//2)-1]<lst[0]:
            return  findSplit(lst[:(len(lst)//2)])    
        elif lst[(len(lst)//2)-1]>lst[0]:
            return findSplit(lst[(len(lst)//2)-1:]) + len(lst)//2

    elif len(lst)%2 != 0:
        if lst[(len(lst)//2)]<lst[0]:    
            return  findSplit(lst[:(len(lst)//2)+1])     
        elif lst[(len(lst)//2)]>lst[0]:    
            return findSplit(lst[(len(lst)//2):]) + len(lst)//2

Now when we print the output we get the correct value.

>>> findSplit([ 66, 81, 83, 96, 13, 19, 30, 41, 44, 57 ])
4

_{I don't understand the second part of your code though ;)}

answered Dec 20, 2015 at 19:46

Bhargav Rao

52.6k29 gold badges130 silver badges142 bronze badges

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

2 Comments

Adrian Hrinko Over a year ago

Thank you very much for your willingness! ;) The second part of my code is simple. You can also enter your own sequence and if you don't enter anything program will operate with list which is pre-defined. Your code is functional but only for pre-defined list ... if I enter different sequence, the result will be incorrect. And that's my problem. I need fully functional code that returns correct answers using various inputs but I'm down in the dumps. But anyway, thank you! :)

Bhargav Rao Over a year ago

@AdrianHrinko I tried to correct your code. :) I will try and give a better answer soon :)

Collectives™ on Stack Overflow

How to find sequence split in list using recursion in Python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related