Question

ASAP!

write a program including   binary-search and merge-sort in Python.

You also need to  modify the code posted and use your variable names and testArrays.  

Answer 1

#1.1) Binary search: Recursive Algorithm

def binarySearchAppr (arr, start, end, x):
# check condition
if end >= start:
mid = start + (end- start)//2
# If element is present at the middle
if arr[mid] == x:
return mid
# If element is smaller than mid
elif arr[mid] > x:
return binarySearchAppr(arr, start, mid-1, x)
# Else the element greator than mid
else:
return binarySearchAppr(arr, mid+1, end, x)
else:
# Element is not found in the array
return -1
arr = sorted(['t','u','t','o','r','i','a','l'])
x ='r'
result = binarySearchAppr(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")

#1.2) Binary search: iterative approach
def binarySearchAppr (arr, start, end, x):
# check condition
if end >= start:
mid = start + (end- start)//2
# If element is present at the middle
if arr[mid] == x:
return mid
# If element is smaller than mid
elif arr[mid] > x:
return binarySearchAppr(arr, start, mid-1, x)
# Else the element greator than mid
else:
return binarySearchAppr(arr, mid+1, end, x)
else:
# Element is not found in the array
return -1
arr = sorted(['t','u','t','o','r','i','a','l'])
x ='r'
result = binarySearchAppr(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")

#Merge sort: Python program
# Python program for implementation of MergeSort

# Merges two subarrays of arr[].
# First subarray is arr[l..m]
# Second subarray is arr[m+1..r]
def merge(arr, l, m, r):
n1 = m - l + 1
n2 = r- m

# create temp arrays
L = [0] * (n1)
R = [0] * (n2)

# Copy data to temp arrays L[] and R[]
for i in range(0 , n1):
L[i] = arr[l + i]

for j in range(0 , n2):
R[j] = arr[m + 1 + j]

# Merge the temp arrays back into arr[l..r]
i = 0 # Initial index of first subarray
j = 0 # Initial index of second subarray
k = l # Initial index of merged subarray

while i < n1 and j < n2 :
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1

# Copy the remaining elements of L[], if there
# are any
while i < n1:
arr[k] = L[i]
i += 1
k += 1

# Copy the remaining elements of R[], if there
# are any
while j < n2:
arr[k] = R[j]
j += 1
k += 1

# l is for left index and r is right index of the
# sub-array of arr to be sorted
def mergeSort(arr,l,r):
if l < r:

# Same as (l+r)//2, but avoids overflow for
# large l and h
m = (l+(r-1))//2

# Sort first and second halves
mergeSort(arr, l, m)
mergeSort(arr, m+1, r)
merge(arr, l, m, r)

# Driver code to test above
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print ("Given array is")
for i in range(n):
print ("%d" %arr[i]),

mergeSort(arr,0,n-1)
print ("\n\nSorted array is")
for i in range(n):
print ("%d" %arr[i]),