Scribd
Upload
23 views3 pages

Tutorial 7: Write Recursive Solution For Following Data Structure Algorithms Using Python. A. Merge Sort

The document provides Python implementations for two recursive algorithms: merge sort and binary search. The merge sort function splits an array into halves, sorts them, and merges them back together, while the binary search function recursively searches for an element in a sorted array. Both algorithms include example usage and output results.

Uploaded by

KAJAL
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
23 views3 pages

Tutorial 7: Write Recursive Solution For Following Data Structure Algorithms Using Python. A. Merge Sort

The document provides Python implementations for two recursive algorithms: merge sort and binary search. The merge sort function splits an array into halves, sorts them, and merges them back together, while the binary search function recursively searches for an element in a sorted array. Both algorithms include example usage and output results.

Uploaded by

KAJAL
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

2180711_Python 180213107009

Tutorial 7:
Write recursive solution for following data structure algorithms using python.

A. Merge sort

# Program

def mergeSort(number):
print("Splitting ",number)
if len(number)>1:
mid = len(number)//2
lefthalf = number[:mid]
righthalf = number[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i=j=k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
number[k]=lefthalf[i]
i=i+1
else:
number[k]=righthalf[j]
j=j+1
k=k+1

while i < len(lefthalf):


number[k]=lefthalf[i]
i=i+1
k=k+1
while j < len(righthalf):
number[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",number)

number = [15,30,28,36,5,23,3]
mergeSort(number)
print(number)
2180711_Python 180213107009

Output

B. Binary search
# Program

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


if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)

else:
return -1
arr = [15,30,28,36,5,23,12,42]
x = 42
result = binary_search(arr, 0, len(arr)-1, x)

if result != -1:
print("Element is present at index", str(result))
else:
print("Element is not present in array")
2180711_Python 180213107009

Output

You might also like