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
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