searching

//searching master program

#include <stdio.h>
#include <stdlib.h>
#include "rand_range.c"
#include <time.h>
#include <stdbool.h>


#define True 1
#define False 0

void swap(int *x, int *y)
{
    *x = *x ^ *y;
    *y = *x ^ *y;
    *x = *x ^ *y;
}

int linear_search(int *ar, int len, int key)
{
    //naiive linear search
    int i;

    for (i = 0; i < len; i ++)
    {
        if (ar[i] == key)
            break;
    }

    return i;
}

int binary_search_iter(int *ar, int len, int key)
{
    //iterative binary search on a sorted list
    int low, high, mid;
    short int found = False;
    int loop_ctr = 0;

    low = 0;
    high = len;

    while (low <= high)
    {
        loop_ctr ++;

        mid = (low + high) / 2;
        //printf("\nlow = %d, high = %d, mid = %d, ar[mid] = %d", low, high, mid, ar[mid]);
        if (ar[mid] < key)
            low = mid + 1;

        else if (ar[mid] > key)
            high = mid - 1;

        else
        {
            break;
        }
    }

    return loop_ctr;
}

int binary_search_rec_aux(int *ar, int len, int key, int low, int high)
{
    //auxilliary function for recursive binary search on a sorted list
    int mid;
    mid = (low + high) / 2;

    if (low > high)
        return False;

    if (ar[mid] < key)
        binary_search_rec_aux(ar, len, key, mid + 1, high);

    else if (ar[mid] > key)
        binary_search_rec_aux(ar, len, key, low, mid - 1);

    else
        return True;
}

int binary_search_rec(int *ar, int len, int key)
{
    return binary_search_rec_aux(ar, len, key, 0, len);
}

int interpolation_search1(int* sortedArray, int len, int key)
{
  // Returns index of key in sortedArray, or -1 if not found
    int low = 0;
    int mid;
    int high = len - 1;
    int loop_ctr = 0;

    while (sortedArray[low] <= key && sortedArray[high] >= key)
    {
        loop_ctr ++;
        mid = low + (((key - sortedArray[low]) / (sortedArray[high] - sortedArray[low])) * (high - low));  //out of range is possible  here

        if (sortedArray[mid] < key)
            low = mid + 1;

        else if (sortedArray[mid] > key)
           // Repetition of the comparison code is forced by syntax limitations.
            high = mid - 1;
        else
            return loop_ctr;
    }

    return loop_ctr; // Not found
}

int interpolation_search(int *a, int bottom, int top, int item)
{

    int mid;
    int loop_ctr = 0;

    while (bottom <= top)
    {
        loop_ctr ++;
        mid = bottom + (top - bottom) * ((item - a[bottom]) / (a[top] - a[bottom]));

        if (item == a[mid])
            break;

        if (item < a[mid])
            top = mid - 1;

        else
            bottom = mid + 1;
    }

    return loop_ctr;
}

void array_printer(int *ar, int len)
{
    int i;
    printf("\n");

    for (i = 0; i < len; i ++)
        printf("%d\t", ar[i]);

    printf("\n");
}


int* random_gen(int len)
{
    bool *flag;
    int *random_nos;
    int i, r;

    flag = (bool *) calloc (2*len, sizeof(bool));
    random_nos = (int *) calloc(len, sizeof(int));

    srand(time(NULL));
    i = 0;

    while (i < len)
    {
        r = rand() % (2*len) + 1;

        if (!flag[r-1])
        {
            flag[r-1] = true;
            random_nos[i ++] = r;
        }
    }

    return random_nos;
}



int* merge(int *left, int len_left, int *right, int len_right)
{
    //merges the two sorted arrays into a single sorted array
    int *merged_arr, len = 0;
    int right_idx = 0, left_idx = 0;

    merged_arr = (int *) calloc(len_right + len_left, sizeof(int));

    while (len != len_right + len_left)
    {
        if ((left_idx >= len_left) && (right_idx < len_right)) //the left array has exhausted
            merged_arr[len ++] = right[right_idx ++];

        else if ((right_idx >= len_right) && (left_idx < len_left)) //the right array has exhausted
            merged_arr[len ++] = left[left_idx ++];

        else
        {
            if (left[left_idx] < right[right_idx])
                merged_arr[len ++] = left[left_idx ++];
            else
                merged_arr[len ++] = right[right_idx ++];
        }

        //array_printer(merged_arr, len_right + len_left);
    }

    free(left);
    free(right);

    return merged_arr;
}

int* merge_sort(int *ar, int len)
{
    int *right, *left, i, j, len_left, len_right;

    if (len < 2)
        return ar;
    else
    {
        len_left = len / 2;
        len_right = len / 2;

        if (len % 2 != 0)
            len_left += 1;

        left = (int *) calloc(len_left, sizeof(int));
        right = (int *) calloc(len_right, sizeof(int));

        for (i = 0; i < len_left; i ++)
            left[i] = ar[i];


        for (j = 0; j < len_right; j ++)
            right[j] = ar[i++];

        //array_printer(left, len_left);
        //array_printer(right, len_right);

        left  = merge_sort(left, len_left);
        right = merge_sort(right, len_right);

        return merge(left, len_left, right, len_right);
    }
}

int main()
{
    int *ar, len = 5, key = rand() % len + 1;
    int n, num_trials = 50;
    int size;
    float total_comparsions;


    //ar = rand_range(len);
    //ar = random_gen(len);
    //ar = merge_sort(ar, len);
    //array_printer(ar, len);

    /*

    n = 0;

    size = 10;

    while(size <= 10000000)
    {
        total_comparsions = 0.0;
        num_trials = 3;
        //ar = (size);
        len = size;

        while (num_trials)
        {
            ar = random_gen(len);
            key = rand() % (2*len) + 1;

            total_comparsions += linear_search(ar, len, key);
            num_trials --;
        }

        total_comparsions /= 3;
        printf("\nLINEAR SEARCH %.2f comparisons for size %d", total_comparsions, size);
        size *= 10;
    }
    /*
    printf("\nLINEAR SEARCH\naverage no of comparisons = %d, total no of comparisons = %d\n", total_comparsions / num_trials, total_comparsions);


    size = 10;

    while(size <= 1000000)
    {
        total_comparsions = 0.0;
        num_trials = 3;
        //ar = (size);
        len = size;

        while (num_trials)
        {
            ar = random_gen(len);
            ar = merge_sort(ar, len);

            key = rand() % (2*len) + 1;

            total_comparsions += binary_search_iter(ar, len, key);
            num_trials --;
        }

        total_comparsions /= 3;
        printf("BINARY SEARCH %.2f comparisons for size %d\n", total_comparsions, size);
        size *= 10;
    }
    */

    size = 10;


    while(size <= 10000000)
    {
        total_comparsions = 0.0;
        num_trials = 3;
        //ar = (size);
        len = size;

        while (num_trials)
        {
            ar = random_gen(len);
            ar = merge_sort(ar, len);

            key = rand() % (2 * len) + 1;

            //total_comparsions += interpolation_search(ar, 0, len, key);
            total_comparsions += interpolation_search1(ar, len, key);

            num_trials --;
        }

        total_comparsions /= 3;
        printf("INTERPOLATION SEARCH %.2f comparisons for size %d\n", total_comparsions, size);
        size *= 10;
    }

    return 0;
}