在列表中搜索一对整数的算法

问题描述 投票:1回答:1

我对算法很新,我遇到了一个问题,我的方法无法正常工作。这是前提条件:

您将获得n对整数的列表L=[(a1,b1),…,(an,bn)]。对于任何两对(ai,bi)∈L(aj,bj)∈L,使得1≤i≤j≤n,我们(至少)有三种情况之一:

  • =今天和b =响个不停
  • 这个<今天
  • 比 < 北京

例如,列表L=[(1,2),(1,1)]无效。有效列表的示例是:

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

问题是:写一个递归函数,应用分而治之的范式来搜索一对给定的值(x,y)是否在L中。

以下是我的python代码,它不能按预期工作:

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   
python algorithm list divide-and-conquer
1个回答
3
投票

你总是挑选一半,但在某些情况下你不知道要搜索哪一半。你可以做以下几点来解决它:

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
© www.soinside.com 2019 - 2024. All rights reserved.