fds4

arr_names=['James','William','Jacob','Sophia','Parth','Vaishnavi','Mohan','Rohan',"Sania",'Sita','Rita','Jim',
'Nilesh','Kabir','Sonam']
#arr_roll=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]
print("\n""list of students attending the program",arr_names)
name=input("\n""Enter name of the student to Check if attended the program:")

index=arr_names.index(name)

n=len(arr_names)
#m=len(arr_roll)

def linear_search(arr_names,name,n):
print("---------Searching by linear search --------")
for i in range(0,n):
if (name==arr_names[i]):
print(name,"having rollno ",index,"has attended the program!! ")
#else:
#print("Student not found!!!!")

result=linear_search(arr_names,name,n)

print("---------BY BINARY SEARCH-------")
def binary_search(arr_names,low,high,name):
mid=(low+high)//2
while low<=high:
if(arr_names[mid]==name):
return arr_names[mid]
elif arr_names[mid]>name:
return binary_search(arr_names,low,mid-1,name)
else:
return binary_search(arr_names,mid+1,high,name)

return -1

result=binary_search(arr_names,0,len(arr_names)-1,name)

if result==-1:
print(name,"having rollno ",index,"has attended the program!! ")

else:
print("Student not found!!!!")

print("--------BY FIBONACCI SEARCH---------")

def fibonacci_search(arr_names,name):
fib2=0
fib1=1
fib3=fib1+fib2

while fib3<n:
    fib2=fib1
    fib1=fib3
    fib3=fib1+fib2

offset=-1

while fib3>1:
    i=min(offset + fib2,n-1)

    if arr_names[i]<name:
        fib3=fib1
        fib1=fib2
        fib2=fib3-fib1
        offset=i

    elif  arr_names[i]>name:
        fib3=fib2
        fib1=fib1-fib2
        fib2=fib3-fib1

    else:
        return i

if fib1 and arr_names[offset]==name:
    return offset 
return -1

result=fibonacci_search(arr_names,name)
if result==-1:
print(name,"having rollno",index,"has attended the program!! ")

else:
print("Student not found!!!!")