Untitled
unknown
python
4 years ago
3.9 kB
4
Indexable
"""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")
Editor is loading...