C implementation of linear search,interpolation search and binary search-CodePudding

I am a beginner in C and I need help. What I am trying to do is make an array between (1-100). One of the number in the array will gone and it call missing number. The output will be the "missing number" in the array. I need to demonstrate the the implementation of linear search, interpolation search and binary search to solve the problem.

The problem is the output always same with the array which has been declared. It was fun playing with coding but I really need help to solve this task.

#include <stdio.h>
#include <time.h>

int MissingNum(int a[], int n)
{
    int i, total;
    total = (n   1) * (n   2) / 2;
    for (i = 0; i < n; i  )
        total -= a[i];
    return total;
}

int LS(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i  )
        if (arr[i] == x)
            return i;
    return -1;
}

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

        if (arr[mid] == x)
            return mid;

        if (arr[mid] > x)
            return BS(arr, l, mid - 1, x);

        return BS(arr, mid   1, r, x);
    }
    return -1;
}

int IS(int arr[], int lo, int hi, int x)
{
    int pos;
    
    if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {

        pos = lo   (((double)(hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]));

        if (arr[pos] == x)
            return pos;

        if (arr[pos] < x)
            return IS(arr, pos   1, hi, x);

        if (arr[pos] > x)
            return IS(arr, lo, pos - 1, x);
    }
    return -1;
}


int main(void)
{
    int choice;
    int arr[] = {86, 56, 95, 59, 18, 91, 73, 80, 31, 87, 84, 51, 16, 27, 40, 60, 26, 20, 6, 92, 25,100,
                48, 90, 15, 96, 69, 71, 76, 47, 74, 49, 63, 38, 33, 3, 55, 14, 45, 46, 30, 35, 53, 50,
                62, 39, 42, 10, 88, 17, 77, 9, 72, 81, 37, 82, 21, 61, 43, 78, 23, 58, 83, 12, 54, 13,
                89, 1, 24, 7, 99, 64, 93, 5, 57, 29, 41, 94, 34, 44, 36, 85, 4, 68, 22, 28, 75, 66, 65,
                11, 19, 97, 70, 79, 8, 52, 32, 9, 8, 2, 67};

    int x = MissingNum(arr,99);
    int n = sizeof(arr) / sizeof(arr[0]);
    int process;

    do
    {


    printf("\t\tMissing integer is %d\n\n", x);
    printf("Choose your type of search\n");
    printf("1. Linear search\n");
    printf("2. Binary search\n");
    printf("3. Interpolation search\n\n");
    printf("Insert input: ");
    scanf("%d",&process);


    switch (process)     {
  
     case 1 :  {
        clock_t countstart = clock();
        int result = LS(arr, n, x);
        int length = sizeof(arr)/sizeof(arr[0]);
        printf("List of Integers : \n");
            for (int i = 0; i < length; i  )  {
                printf("%d ", arr[i]);
            }

        if (result == -1)
        {
          printf(" \n\nMissing Integer : %d \n", x);
        }
        clock_t countstop = clock();
        printf("\n\nExecution for Linear Search: %f seconds\n", (double)(countstop - countstart) / CLOCKS_PER_SEC);
        }
        break;

    case 2 : {
        clock_t countstart = clock();
        int output = BS(arr, 0, n - 1, x);
        int length = sizeof(arr)/sizeof(arr[0]);
        printf("List of Integers : \n");
            for (int i = 0; i < length; i  )
            {
                printf("%d ", arr[i]);
            }

            if (output == -1)
            {
                printf(" \n\nBinary Search Integer : %d \n",x);
            }
            clock_t countstop = clock();
            printf("\n\nExecution time for Binary Search: %f seconds\n", (double)(countstop - countstart) / CLOCKS_PER_SEC);


        }
        break;

    case 3 :{
        clock_t countstart = clock();
        int index = IS(arr, 0, n - 1, x);
        int length = sizeof(arr)/sizeof(arr[0]);

        printf("List of Integers : \n");
            for (int i = 0; i < length; i  )
            {
                printf("%d ", arr[i]);
            }

            if (index == -1)
            {
                printf(" \n\nInterpolation Search Integer : %d \n",x);
            }
            clock_t countstop = clock();
            printf("\n\nExecution time for Interpolation Search: %f seconds\n", (double)(countstop - countstart) / CLOCKS_PER_SEC);

        }

        break;
   
    default : printf("Invalid code please try again");
    break;
}
        printf("\n\nDo you want to continue? Enter '1' if YES and '2' if NO : ");
        scanf(" %d" ,&choice);
        }while(choice==1);
        getchar();
    return 0;
}

CodePudding user response：

Please double check , 9, 8, for typos. I suspect you want , there. With , 98, you'd have a cleanly initialised 100 entry array, without a missing number.
With , you'd have a 99 entry array with 98 missing.

I tried and with that typo fix all three algos result in 98 being found.
Replacing a different of the init numbers with 98 then results in that number being found by all three algos.

Your implementations seem questionable to me.

LS looks through the array to check whether the number provided from outside is missing and confirms if it is. That is not actually finding the missing number. For IS and BS practically the same.

Whatever number MissingNum() guesses (and guesses incorrectly), as long as it is not in the array (which is true for anything beyond 100), all three algos will confirm. MissingNum() is guessing incorrectly, because it makes assumptions on the array init (one missing, all others once), which the shown array init does not match. When I tried the guess was 150, probably the same for you. Obviously wrong. The fact that all algos confirm that guess, should have made you suspicious. Fixing the typo as I proposed fixes MissingNum()s assumptions. It guess correctly (98) and all three algos enthusiastically agree - they should be tarred and feathered.