Untitled

"""Write a python programme to store the roll numbers of all the students in an array who attended tthe training programme in a random order.
a)Write function for searching whether particular student attended the training programme or not using
linear search(Done)
sentinal search(Done)
b)Write function for searching whether particular student attended the training programme or not using
binary search
fibonnaci search
"""


def linearSearch(arr1, n, y):  # Linear search

    # Going through array sequencially
    for i in range(0, n):
        if (arr1[i] == y):
            return i + 1
    return -1


def sentinelSearch(arr1, n, y):  # sentinel search
    last = arr1[n - 1]
    arr1[n - 1] = y
    i = 0
    while (arr1[i] != y):
        i += 1

    arr1[n - 1] = last  # Put the last element back

    if ((i < n - 1) or (arr1[n - 1] == y)):
        print(y, " is present at index ", i + 1)
    else:
        print("Roll number not present")


def binsearch(arr1, bottom, top, y):  # Binary search
    arr1.sort()

    if top >= bottom:
        mid = (top + bottom) // 2
        if arr1[mid] == y:
            return mid
        elif arr1[mid] > y:
            return binsearch(arr1, bottom, mid - 1, y)
        else:
            return binsearch(arr1, top, mid + 1, y)
    else:
        return -1


def fibgen(s):
    if s < 1:
        return 0
    elif s == 1:
        return 1
    else:
        return fibgen(s - 1) + fibgen(s - 2)


def fibsearch(arr1, y):
    arr1.sort()
    m = 0
    while (fibgen(m) < len(arr1)):
        m = m + 1
    offset = -1
    while (fibgen(m) > 1):

        i = min(offset + fibgen(m - 2), len(arr1) - 1)

        if (y > arr1[i]):

            m = m - 1
            offset = i

        elif (y < arr1[i]):

            m = m - 2

        else:

            return i

    return -1


# Main block
print("Input of list")
arr1 = []

n = int(input("enter number of students: "))
print('\n')
for i in range(0, n):
    x = int(input("Enter roll number: "))
    arr1.append(x)

print("The list of roll number is: ", arr1)
y = int(input("Enter roll number to be found: "))

while (True):
    print("*" * 10 + "Menu" + "*" * 10)
    print(""" 1. Linear Search
 2. Sentinel Linear seach
 3. Binary search
 4. Fibonnaci search
-1. EXIT """)
    choice = int(input("Enter number for the operation to be performed: "))
    if choice == 1:
        print("*" * 40 + "\n")
        print("Result printed using Linear search\n")
        print("*" * 40 + "\n")

        lsearchresult = linearSearch(arr1, n, y)
        if (lsearchresult == -1):
            print("Roll number not present")
        else:
            print("Roll number present at: ", lsearchresult)
            print('\n')
    elif choice == 2:
        print("*" * 40 + "\n")
        print("Result printed using Sentinel search\n")
        print("*" * 40 + "\n")
        sentinelSearch(arr1, n, y)
        print("\n")
        print("*" * 40 + "\n")

    elif choice == 3:
        print("*" * 40 + "\n")
        print("Original list",arr1)

        print("Result printed using Binary search\n")
        print("*" * 40 + "\n")
        ans = binsearch(arr1, 0, len(arr1) - 1, y)
        print("Sorted list", sorted(arr1))
        if ans != -1:
            print("Roll number present at index ", str(ans + 1))
        else:
            print("Roll number not present")

    elif choice == 4:
        print("*" * 40 + "\n")
        print("Result printed using Fibonacci search\n")
        print("*" * 40 + "\n")
        u = fibsearch(arr1, y)
        if u != -1:
            print("Roll number present at index ", str(u + 1))
        else:
            print("Roll number not present")



    elif choice == -1:

        break
    else:
        print("Please enter valid choice")