Q:

Checking duplicates with divide and conquer

To search duplicates in nlogn I decided to use a merge sort modified.
The main problem is that an error appear and I don't know how to fix this problem: Results sometimes are completely wrong.
My algorithm has to return True if it found a pair( an element with the same value) or False if it has not a pair. All this must be done inside the divide and conquer algorithm.(no extra for loop ecc.)
This is the code
def check_duplicates(X):   
    if len(X)>1:
        mid = len(X)//2
        lefthalf = X[:mid]
        righthalf = X[mid:]

        check_duplicates(lefthalf)
        check_duplicates(righthalf)

        i=0
        j=0
        k=0
        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i] == righthalf[j]:
                return True

            if lefthalf[i]<righthalf[j]:
                X[k]=lefthalf[i]
                i=i+1
            else:
                X[k]=righthalf[j]
                j=j+1
            k=k+1

        while i<len(lefthalf):
            X[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j<len(righthalf):
            X[k]=righthalf[j]
            j=j+1
            k=k+1

   return False

Let's make some examples:
let X=[1,2,3] the function returns false, it's ok.
let X=[1,3,2] the function returns false, which is also ok.
The main problem are with this cases:
let X=[1,3,3] the function returns false, which is wrong(should return true).
let X=[4,6,6] the function returns false, which is wrong and so on.
The main problem is when I put two same values at the end of the list, and I have no idea how to fix it...
ps: i apologise for my english

A:

You forgot that if you do the recursive call, and the call results in True, to return True as well: thus, modify the recursive call to:
if(check_duplicates(lefthalf)) :
    return True

Or the full (indented) version reads:
def check_duplicates(X):   
    if len(X)>1:
        mid = len(X)//2
        lefthalf = X[:mid]
        righthalf = X[mid:]
        if(check_duplicates(lefthalf)) :
            return True
        if(check_duplicates(righthalf)) :
            return True
        i=0
        j=0
        k=0
        while i<len(lefthalf) and j<len(righthalf) :
            if lefthalf[i] == righthalf[j]:
                return True
            if lefthalf[i]<righthalf[j]:
                X[k]=lefthalf[i]
                i=i+1
            else:
                X[k]=righthalf[j]
                j=j+1
            k=k+1

        while i<len(lefthalf):
            X[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j<len(righthalf):
            X[k]=righthalf[j]
            j=j+1
            k=k+1

    return False

In the while loop, you only check for cross-equality (equal elements in the two sublists). But the result in your version is only returned if it return Trues on the top level comparison.
You in other words forgot to propagate the True value in the call stack.

