Search code examples
pythonalgorithmrecursiondivide-and-conquer

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

I'm trying to implement following picture.

enter image description here

The logic this illustrates is as follows: compare the first entity and last entity of a block and if they are different, divide it into two blocks. Then, compare the first and last entity of the divided block. Repeat it until we find two entities that are the same.

I've newly started to program and I just learned recursive logic, stacks and queues. I'm trying to implement it with DFS but I'm not sure how I can divide it into two and repeat. Can you help me to find a keyword to Google it? Or is there any matching data structure I can use?

I wrote this code, but this doesn't seem to work.

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():
Solution

  • DFS is not relevant here, Use recursion to implement the picture. Think about the easiest case (a condition in which the function returns the answer - 2 entities that are either equal or not) and continue from that point.