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

Popular posts from this blog

Python Program To Store Marks

Currency.txt

Python Comprehensions