Finding list item in another list using fabonnaci search

Question

This is a Fibonacci search function. It take integer(y) and and search in x(which is a list of integers)

def FibonacciSearch(lys, val):
    fibM_minus_2 = 0
    fibM_minus_1 = 1
    fibM = fibM_minus_1 + fibM_minus_2
    while (fibM < len(lys)):
        fibM_minus_2 = fibM_minus_1
        fibM_minus_1 = fibM
        fibM = fibM_minus_1 + fibM_minus_2
    index = -1;
    while (fibM > 1):
        i = min(index + fibM_minus_2, (len(lys)-1))
        if (lys[i] < val):
            fibM = fibM_minus_1
            fibM_minus_1 = fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
            index = i
        elif (lys[i] > val):
            fibM = fibM_minus_2
            fibM_minus_1 = fibM_minus_1 - fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
        else :
            return i
    if(fibM_minus_1 and index < (len(lys)-1) and lys[index+1] == val):
        return index+1;
    return -1
x = [1,2,3,4,5,6,7,8,9,10,11]
y = 4
for i in x:
    if i == y:
        print("Found on index", FibonacciSearch(x, y))
        
    else:
        pass

This function only take x list of integers and y (integer) and return index value in list x. I am trying to modify this function as

def FibonacciSearch(lys, val):
    fibM_minus_2 = 0
    fibM_minus_1 = 1
    fibM = fibM_minus_1 + fibM_minus_2
    while (fibM < len(lys)):
        fibM_minus_2 = fibM_minus_1
        fibM_minus_1 = fibM
        fibM = fibM_minus_1 + fibM_minus_2
    index = -1;
    while (fibM > 1):
        i = min(index + fibM_minus_2, (len(lys)-1))
        if (lys[i] < val):
            fibM = fibM_minus_1
            fibM_minus_1 = fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
            index = i
        elif (lys[i] > val):
            fibM = fibM_minus_2
            fibM_minus_1 = fibM_minus_1 - fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
        else :
            return i
    if(fibM_minus_1 and index < (len(lys)-1) and lys[index+1] == val):
        return index+1;
    return -1
x = ["2d","4c","6f","9g","10e","11p"]
y = ["2d","6f","9g"]
for i in x:
    for i in y:
        if i == y:
            print("Found on index", FibonacciSearch(x, y))
        else:
            pass

This program does not return anything. Infact this program should take each item from y list and match with x list and return index value according to the FibonacciSearch(x,y) function.

user_12932447 · Answer

You are making confusion here

for i in x:
    for i in y:
        if i == y:
            print("Found on index", FibonacciSearch(x, y))
        # writing "else: pass" is useless

You are looping two times over i. I guess you need something like

for i in x:
    for j in y:
        if i == j:
            print("Found on index", FibonacciSearch(i, j))
        else:
            pass

With this modification, the script will return

Found on index -1
Found on index -1
Found on index -1

which I don't think it's what you want but at least it's something.

You should also get rid of add the statement-terminating semicolons, even if it will not solve your problem.

Finding list item in another list using fabonnaci search

1 Answers