Question

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

it has to output the following:

NeArr range(0, 20)                                                                                                          

result for searching 6 True                                                                                                 

result for searching 16 False  

                                                                                                                          

for-loop's function                                                                                                         

arr range(0, 15)                                                                                                            

for-loop's func result for searching 6 1                                                                                    

result for searching 16 0

it has to be a simple code and please!! put the whole code together.

Answer 1

Question is not clear .

i am writing with my understanding.

please leave a comment if you need anything else.

COde:

def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r- m

    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]

    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

    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

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)
def binarySearch (arr, l, r, x):

    # Check base case
    if r >= l:

        mid = l + (r - l) // 2

        # If element is present at the middle itself
        if arr[mid] == x:
            return 1

        # If element is smaller than mid, then it
        # can only be present in left subarray
        elif arr[mid] > x:
            return binarySearch(arr, l, mid-1, x)

        # Else the element can only be present
        # in right subarray
        else:
            return binarySearch(arr, mid + 1, r, x)

    else:
        # Element is not present in the array
        return 0
Nearr=[range(0,15)]
mergeSort(Nearr,0,len(Nearr)-1)
r=binarySearch(Nearr,0,len(Nearr),6)
print(bool(r))
r=binarySearch(Nearr,0,len(Nearr),16)
print(bool(r))

This code first sort the array using mergesort and searches the array using binary search.

OUTPUT: