Binary search:

# arr: sorted list in which we are searching

# low: beginning index of the current portion being checked

# high: ending index of the current portion being checked

# key: element we want to locate

def binary_search(arr, low, high, key):

# Continue searching only if the range is valid

if low <= high:

# Calculate middle index of current search range

mid = (low + high) // 2

# If the middle element matches the key, return its index

if arr[mid] == key:

return mid

# If the key is smaller than the middle element,

# search in the left sub-array

elif key < arr[mid]:

return binary_search(arr, low, mid - 1, key)

else:

return binary_search(arr, mid + 1, high, key)

# If low exceeds high, the element is not present

return -1

# Sample data

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72]

key = 23

# Perform search

result = binary_search(arr, 0, len(arr) - 1, key)

# Output result

if result == -1:

print("The element is not present in the list.")

else:

print("The element is located at index:", result)

Output:
 MERGE SORT:
def merge_sort(arr, low, high):

# If the starting index becomes greater than or equal to ending index,

# it means the sub-array has 0 or 1 element and is already sorted.

if low >= high: # base case

return

# Calculate the middle index of the current portion of the array

# Integer division is used so the result is a whole number

mid = (low + high) // 2 # (0 + 5) // 2 = 5 // 2 = 2

# Print statement to show how the array is being divided

print("Now low is =", low, "High is =", high, "and Mid value =", mid)

# Recursively sort the first half of the array

# Recursively sort the second half of the array

merge_sort(arr, mid + 1, high)

# Merge the two sorted halves into one sorted portion

merge(arr, low, mid, high)

def merge(arr, low, mid, high):

# Create temporary arrays for left and right halves

left = arr[low:mid + 1]

right = arr[mid + 1:high + 1]

# i is index for left array

i=0

# j is index for right array

j=0

# k is index for placing elements back into the original array

k = low
# Compare elements from left and right arrays

# and insert the smaller element into original array

while i < len(left) and j < len(right):

if left[i] <= right[j]:

arr[k] = left[i] # Place left element into main array

i += 1 # Move to next element in left array

else:

arr[k] = right[j] # Place right element into main array

j += 1 # Move to next element in right array

k += 1 # Move to next position in main array

# If any elements remain in left array, copy them

while i < len(left):

arr[k] = left[i]

i += 1

k += 1

# If any elements remain in right array, copy them

while j < len(right):

arr[k] = right[j]

j += 1
 k += 1

# Example usage

numbers = [38, 27, 43, 3, 9, 82, 10]

# Call merge sort on the full array

merge_sort(numbers, 0, len(numbers) - 1)

# Print the sorted array

print(numbers)

OTUPUT:
Tower of Hanoi
# Tower of Hanoi using recursion

# This function moves 'n' disks from source peg to destination peg

# using auxiliary peg as helper.

def tower_of_hanoi(n, source, auxiliary, destination):

# Base case:

# If there is only one disk, directly move it from source to destination.

if n == 1:

print("Move disk 1 from", source, "to", destination)

return

# Step 1:

# Move the top n-1 disks from source to auxiliary peg

# (using destination as temporary support).

tower_of_hanoi(n - 1, source, destination, auxiliary)

# Step 2:

# Move the largest disk (nth disk) from source to destination.

print("Move disk", n, "from", source, "to", destination)

# Move the n-1 disks from auxiliary to destination

# (using source as temporary support).

tower_of_hanoi(n - 1, auxiliary, source, destination)

# Example usage

n = int(input("Enter number of disks: ")) # Take number of disks from user

# Call the function with peg names A, B, C

tower_of_hanoi(n, 'A', 'B', 'C')

OUTPUT:
Fibonacci :
# Fibonacci class that stores previously computed values to avoid repeated work.

# After computing Fib(k) once, future requests for the same (or smaller) k are instant.

class Fibonacci:

# Initialize the object and create a small table of known Fibonacci numbers.

def __init__(self):

# cache[0] == Fib(0) and cache[1] == Fib(1).

# We will append new Fibonacci numbers here as they are computed.

[Link] = [0, 1]

# Make the object callable so we can use fib_instance(n) syntax.

def __call__(self, n):

# Input validation: only non-negative integers make sense for Fibonacci.

if not (isinstance(n, int) and n >= 0):

raise ValueError(f"Expected a non-negative integer, got {n!r}")

# If we already computed Fib(n), return it right away from the cache.

if n < len([Link]):

return [Link][n]

else:

# Compute any missing Fibonacci numbers from the current cache size up to n.
 # This loop only computes each needed value once and stores it for later.

for i in range(len([Link]), n + 1):

# Use the recurrence relation: Fib(i) = Fib(i-1) + Fib(i-2)

next_value = [Link][i - 1] + [Link][i - 2]

# Append the newly computed value so it is available for future calls.

[Link](next_value)

# After filling the cache up to index n, return the requested value.

return [Link][n]

# Example usage:

fib = Fibonacci() # create the Fibonacci object (cache starts as [0,1])

num = int(input("Enter a non-negative integer: ")) # read the requested index

print(f"Fibonacci({num}) =", fib(num)) # compute & print Fib(num)