Answer to Question #126396 in C++ for Jamal Haider

Question

Consider the following sequence. Apply merge sort algorithm to sort the given data and
then apply binary search to find the element 30 in the array.
12, 56, 12, 45, 45, 45, 33, 5, 5, 5, 27, 27, 27, 27,30

Answer 1

#include <cstdio>
#include <iostream>


using namespace std;


// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;


    /* create temp arrays */
    int L[n1], R[n2];


    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        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 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }


    /* Copy the remaining elements of L[], if there
       are any */
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }


    /* Copy the remaining elements of R[], if there
       are any */
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}


/* l is for left index and r is right index of the
   sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
    if (l < r) {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l + (r - l) / 2;


        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);


        merge(arr, l, m, r);
    }
}


int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;


        // If the element is present at the middle
        // itself
        if (arr[mid] == x)
            return mid;


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


        // Else the element can only be present
        // in right subarray
        return binarySearch(arr, mid + 1, r, x);
    }


    // We reach here when element is not
    // present in array
    return -1;
}




/* Function to print an array */
void printArray(int A[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}




int main()
{
    int arr[] = { 12, 56, 12, 45, 45, 45, 33, 5, 5, 5, 27, 27, 27, 27,30 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);


    cout <<"Given array is \n";
    printArray(arr, arr_size);


    mergeSort(arr, 0, arr_size - 1);


    cout <<"\nSorted array is \n";
    printArray(arr, arr_size);


    int x = 30;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1) ? cout << "\nElement is not present in array"
                   : cout << "\nElement is present at index " << result;
    return 0;
}

output: