# Untitled

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):
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(""" 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: