Skip to content

Instantly share code, notes, and snippets.

@hasinur1997
Created September 22, 2019 18:03
Show Gist options
  • Save hasinur1997/03e685947db3f351ff67b7e1fbbc4711 to your computer and use it in GitHub Desktop.
Save hasinur1997/03e685947db3f351ff67b7e1fbbc4711 to your computer and use it in GitHub Desktop.
Merge sort and binary search algorithm

Binary Search and Merge sort algorithm

#include<stdio.h>
#define array_size 100

int arr[array_size];
int temp[array_size];
void merge(int startPoint, int midPoint, int endPoint);

void sort(int startPoint, int endPoint) {
    if(startPoint == endPoint) {
        return;
    }

    int midPoint;

    midPoint = (startPoint + endPoint) / 2;

    sort(startPoint, midPoint);
    sort(midPoint+1, endPoint);
    merge(startPoint, midPoint, endPoint);
}

void merge(int startPoint, int midPoint, int endPoint) {
    int firstArrCount, secondArrCount, i;

    firstArrCount = startPoint;
    secondArrCount = midPoint + 1;

    for(i = firstArrCount; firstArrCount <= midPoint && secondArrCount <= endPoint; i++) {

        if(arr[firstArrCount] < arr[secondArrCount]) {
            temp[i] = arr[firstArrCount++];
        }else{
            temp[i] = arr[secondArrCount++];
        }
    }

    while(firstArrCount <= midPoint) {
        temp[i++] = arr[firstArrCount++];
    }

    while(secondArrCount <= endPoint){
        temp[i++] = arr[secondArrCount++];
    }

    for(i = startPoint; i<=endPoint; i++) {
        arr[i] = temp[i];
    }

}

void binary_search(int array[], int item) {
    int left, right, mid, fount_item = 0;

    left = 0;
    right = sizeof(array) / sizeof(int);

    while(left <= right) {
        mid = (left + right) / 2;

        if(array[mid] == item) {
            fount_item = 1;
            break;
        }

        if(item < array[mid]) {
            right = mid - 1;
        }

        if(item > array[mid]) {
            left = mid + 1;
        }
    }

    if(fount_item == 1) {
        printf("%d  is found\n", item);
    }else{
        printf("%d is not found\n", item);
    }
}

int main() {
    int i, n, item;
    printf("Enter the number of elements\n");
    scanf("%d", &n);

    printf("Enter %d elements\n", n);
    for(i = 0; i<n; i++) {
        scanf("%d", &arr[i]);
    }
    sort(0, n-1);

    for(i = 0; arr[i]; i++) {
        printf("%d\t", arr[i]);
    }

    printf("\n\n");
    printf("Please enter search item: \n");
    scanf("%d", &item);

    binary_search(arr, item);

}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment