CODEWITHSUNDEEP
pythonalgorithmlistdivide-and-conquer
Alex Wang
Alex Wang

Reputation: 481

Algorithm of searching for a pair of integers in a list

I'm quite new to algorithm and I encountered a question to which my approach does not works properly. Here's the precondition:

You are given a list L=[(a1,b1),…,(an,bn)] of n pairs of integers. For any two pairs (ai,bi)∈L and (aj,bj)∈L such that 1≤i≤j≤n , we have (at least) one of three cases:

For example, the list L=[(1,2),(1,1)] would not be valid. An example of a valid list is: 

L = [(0,1), (1, 0), (0, 1), (1, 1), (1, 2), (3, 1), (3, 1), (2, 2), (2, 3), (3, 2), (2, 3), (4, 3), (3, 4), (4, 4), (4, 5), (5, 5)]

The question is: Write a recursive function that applies the divide-and-conquer paradigm to search if a given pair of values (x, y) is in L.

The following is my python code which doesn't work as expected:

def pair_search(l, p):
    found = False
    calls = 1

    if len(l) == 0:
        return found, calls
    if len(l) == 1:
        if l[0] == p:
            found = True
        return found, calls

    mid = len(l) // 2

    if p == l[mid]:
        found = True
        return found, calls
    elif (l[mid][0] == p[0] and l[mid][1] == p[1]) or l[mid][0] < p[0] or l[mid][1] < p[1]:
        f, c = pair_search(l[mid + 1:], p)   
    else:
        f, c = pair_search(l[:mid], p)
    found = f or found
    calls += c
    return found, calls

Upvotes: 1

Views: 541

Answers (1)

user2390182
user2390182

Reputation: 73460

You always pick one half, but in some cases you can't know which half to search in. You can do the following to fix it:

def pair_search(l, p):
    if not l:
        return False, 1
    mid = len(l) // 2
    m = l[mid]  # pair in the middle
    if p == m:
        return True, 1
    if p[0] <= m[0] and p[1] <= m[1]:  
        # both smaller (or equal), must be in lower half
        f, c = pair_search(l[:mid], p)
        return f, c + 1 
    if p[0] >= m[0] and p[1] >= m[1]:  
        # both bigger (or equal), must be in upper half
        f, c = pair_search(l[mid+1:], p)
        return f, c + 1 
    # one smaller, one bigger: could be in either half
    f1, c1 = pair_search(l[:mid], p)
    if f1:  # found, so don't look any further
        return f1, c1 + 1
    f2, c2 = pair_search(l[mid+1:], p)
    return f2, c1 + c2 + 1

Upvotes: 3

Related Questions