Ternary Search
# Q13. Write A Python Program To Maintain Club Members, Sort On Roll Numbers InAscending Order.
# Write Function 'Ternary Search' To Search whether A Particular Student Is AMember Of Club Or Not.
# Ternary Search Is Modified Binary Search That Divides Array Into 3 HalvesInstead Of 2.
# Ternary Search
arr = []
def TakeInput():
num = int(input("Enter The Number Of Students\n"))
for i in range(num):
students = int(input(f"Enter The Roll No Of Student {i + 1}\n"))
arr.append(students)
print("\nArray Of Total Students =", arr, "\n")
def bubbleSort(array):
n = len(array)
print("\nUnsorted Array Of Total Students =", arr)
flag = 0
for i in range(n):
for j in range(n - i - 1):
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
flag = 1
if flag == 0:
break
print("Sorted Array Of Total Students =", arr, "\n")
def TernarySearchWithRecursion(low, high, array, num_to_find):
mid1 = low + (high - low) // 3
mid2 = low + 2 * (high - low) // 3
if num_to_find == array[low]:
return f"The Number is Present At Index {low}\n"
elif num_to_find == array[high]:
return f"The Number is Present At Index {high}\n"
elif num_to_find == array[mid1]:
return f"The Number is Present At Index {mid1}\n"
elif num_to_find == array[mid2]:
return f"The Number is Present At Index {mid2}\n"
elif num_to_find <= array[mid1]:
return TernarySearchWithRecursion(low, mid1 - 1, array, num_to_find)
elif num_to_find >= array[mid2]:
return TernarySearchWithRecursion(mid2 + 1, high, array, num_to_find)
else:
return TernarySearchWithRecurlow(mid1 + 1, mid2, array, num_to_find)
return -1
def TernarySearchWithoutRecursion(array, num_to_find):
left = 0
right = len(array) - 1
while left <= right:
mid1 = left + (right - left) // 3
mid2 = left + 2 * (right - left) // 3
if num_to_find == array[left]:
return f"The Number is Present At Index {left}\n"
elif num_to_find == array[right]:
return f"The Number is Present At Index {right}\n"
elif num_to_find < array[left] or num_to_find > array[right]:
return -1
elif num_to_find <= array[mid1]:
right = mid1
elif num_to_find > arr[mid1] and num_to_find <= array[mid2]:
left = mid1 + 1
right = mid2
else:
left = mid2 + 1
return -1
while True:
try:
userinput = int(input("1. Press 1 To Accept And Print Student Roll Numbers\n2. Press 2 For Sorting The Array\n3. Press 3 For Ternary Search With Recursion\n4. Press 4 For Ternary Search Without Recursions\n5. Press 5 To Exit\n\n"))
if userinput == 1:
TakeInput()
elif userinput == 2:
bubbleSort(arr)
elif userinput == 3:
left = 0
right = len(arr) - 1
num_to_find = int(
input("\nEnter The Number You Want To Find In The Array\n"))
print(TernarySearchWithRecursion(left, right, arr, num_to_find))
elif userinput == 4:
num_to_find = int(
input("\nEnter The Number You Want To Find In The Array\n"))
print(TernarySearchWithoutRecursion(arr, num_to_find))
elif userinput == 5:
print("Exit")
break
except Exception as e:
print("Wrong Input, Please Enter Integers Only !!\n")
# Output
# 1. Press 1 To Accept And Print Student Roll Numbers
# 2. Press 2 For Sorting The Array
# 3. Press 3 For Ternary Search With Recursion
# 4. Press 4 For Ternary Search Without Recursions
# 5. Press 5 To Exit
# 1
# Enter The Number Of Students
# 10
# Enter The Roll No Of Student 1
# 24
# Enter The Roll No Of Student 2
# 22
# Enter The Roll No Of Student 3
# 21
# Enter The Roll No Of Student 4
# 12
# Enter The Roll No Of Student 5
# 11
# Enter The Roll No Of Student 6
# 9
# Enter The Roll No Of Student 7
# 45
# Enter The Roll No Of Student 8
# 48
# Enter The Roll No Of Student 9
# 44
# Enter The Roll No Of Student 10
# 54
# Array Of Total Students = [24, 22, 21, 12, 11, 9, 45, 48, 44, 54]
# 1. Press 1 To Accept And Print Student Roll Numbers
# 2. Press 2 For Sorting The Array
# 3. Press 3 For Ternary Search With Recursion
# 4. Press 4 For Ternary Search Without Recursions
# 5. Press 5 To Exit
# 2
# Unsorted Array Of Total Students = [24, 22, 21, 12, 11, 9, 45, 48, 44, 54]
# Sorted Array Of Total Students = [9, 11, 12, 21, 22, 24, 44, 45, 48, 54]
# 1. Press 1 To Accept And Print Student Roll Numbers
# 2. Press 2 For Sorting The Array
# 3. Press 3 For Ternary Search With Recursion
# 4. Press 4 For Ternary Search Without Recursions
# 5. Press 5 To Exit
# 3
# Enter The Number You Want To Find In The Array
# 48
# The Number is Present At Index 8
# 1. Press 1 To Accept And Print Student Roll Numbers
# 2. Press 2 For Sorting The Array
# 3. Press 3 For Ternary Search With Recursion
# 4. Press 4 For Ternary Search Without Recursions
# 5. Press 5 To Exit
# 4
# Enter The Number You Want To Find In The Array
# 48
# The Number is Present At Index 8
# 1. Press 1 To Accept And Print Student Roll Numbers
# 2. Press 2 For Sorting The Array
# 3. Press 3 For Ternary Search With Recursion
# 4. Press 4 For Ternary Search Without Recursions
# 5. Press 5 To Exit
# 5
# Exit
Comments
Post a Comment