Untitled

mail@pastecode.io avatar
unknown
python
2 years ago
4.3 kB
2
Indexable
Never
"""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 createarr(list, length):
    i = 0
    while (i < length):
        while (True):
            try:                                                            # Exception Handling
                x = int(input("Enter Roll Number present : "))
                break
            except ValueError:
                print("Enter a valid input")
        # To check whether the Roll Number is repeated
        if (x in list):
            print("Roll Number already present.")
        else:
            list.append(x)
            i += 1
    return list


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, mid+1, top, 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")
A = []
n = int(input("enter number of students: "))
print('\n')
arr1 = createarr(A, n)
print("The list of roll number is: ", arr1)
y = int(input("Enter roll number to be found: "))

while(True):
    print("*"*20+"Menu"+"*"*20)
    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("*"*40+"\n")
        ans = binsearch(arr1, 0, len(arr1)-1, y)
        print("Sorted list", sorted(arr1))
        print("*"*40+"\n")
        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)
        print("Sorted list", sorted(arr1))
        print("*"*40+"\n")
        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")