分而治之算法在子列表中找到两个匹配元素

Question

我正在尝试实现下图。

这说明的逻辑如下：比较块的第一个实体和最后一个实体，如果它们不同，则将其分成两个块。然后，比较分块的第一个和最后一个实体。重复直到我们找到两个相同的实体。

我刚开始编程，刚刚学习了递归逻辑、堆栈和队列。我正在尝试使用 DFS 来实现它，但我不确定如何将它分成两部分并重复。你能帮我找个关键词到Google吗？或者有没有我可以使用的匹配数据结构？

我写了这段代码，但这似乎不起作用。

def getBln(idx1, idx2):
  pass 

#DFS
def videoRcsv():
  if getBln(idx1, idx2) == True:
    break
  else:
    videoRcsv(idx1, idx2/2),videoRcsv(idx2/2, idx2)

def main():
  pass

main():

Answer 1

这里不涉及DFS，用递归实现图片。考虑最简单的情况（函数 returns 答案的条件 - 2 个实体相等或不相等）并从该点继续。

Answer 2

你为什么不使用循环？

    int l = 0; // first block
    
    int r = idx2; // index of last block
       
    while( l < r ){
          if( blocks[l++] == blocks[r--] ){
              // do smth
          }
    }

分而治之算法在子列表中找到两个匹配元素

Divide and conquer algorithm to find two matching elements in a sublist

python

algorithm

recursion

divide-and-conquer