Will find value using binary search using insertion sort. New to coding so cant find the solution. Now if I input any values it doesn't use insertion and can't find the value.

#include <stdio.h>
int main()
{
int i, low, high, mid, n, key, array[100],size;
printf("Enter number of elements");
scanf("%d",&n);
printf("Enter %d integersn", n);
for(i = 0; i <= n-1; i  )
scanf("%d",&array[i]);
void insertionSort(int array[], int size) {
 for (int step = 1; step <= size-1; step  ) {
   int key = array[step];
   int j = step - 1;

   while (key < array[j] && j >= 0) {
     array[j   1] = array[j];
     --j;
   }
   array[j   1] = key;
 }
}
  printf("%d\n",key);
  scanf("%d", &key);
  low = 0;
  high = n - 1;
  mid = (low high)/2;
  while (low <= high) {
  if(array[mid] < key)
  low = mid   1;
  else if (array[mid] == key) {
  printf("%d\n", key, mid 1);
  break;
}
  else
  high = mid - 1;
  mid = (low   high)/2;
}
  if(low > high)
  printf("%d\n", key);
  return 0;
}

CodePudding user response：

I corrected your code.

#include <stdio.h>

void insertionSort(int array[], int size) {
    int key, j;
    for (int step = 1; step < size; step  ) {
        key = array[step];
        j = step - 1;

        while (key < array[j] && j >= 0) {
            array[j   1] = array[j];
            j--;
        }
        array[j   1] = key;
    }
}

int main()
{
    int i, low, high, mid, n, key, array[100],size;
    printf("Enter number of elements");
    scanf("%d",&n);
    printf("Enter %d integersn\n", n);
    for(i = 0; i <= n-1; i  ){
        scanf("%d", &array[i]);
    }
    insertionSort(array, n);
    printf("Insert key\n");
    scanf("%d", &key);
    printf("%d\n",key);
    low = 0;
    high = n - 1;
    mid = (low high)/2;
    while (low <= high) {
        if(array[mid] < key)
            low = mid   1;
        else if (array[mid] == key) {
            printf("key: %d  mid: %d\n", key, mid 1);
            break;
        }
        else
            high = mid - 1;
        mid = (low   high)/2;
    }
    if(low > high)
        printf("%d\n", key);
    return 0;
}

The problems I found were:

1. The function was inside main (remember it can't be done), you can put it after main if with a declaration before it or put it before main.
2. The for guard inside the insertion sort was wrong you have to put step < size and not step <= size - 1
3. As you thought the insertion had to be called every time you cycle inside the for, just call it once after inserting all the elements inside the array
4. You had put the printf of the kay before the scan, this would have printed you random things as the contents of the variable were not clean.

Hope to help.

CodePudding user response：

The problem is that insertionSort is never called on the array after inputting the elements. Instead, you have defined the function insertionSort at the point where it should have been called. Defining a function within another function is not a standard part of the C language, but some compilers may support it as an extension.

If you move the definition of insertionSort outside the main function, and add a call to the function, the code works after fixing a few printf statements. Here is a slightly tidied up, working version:

#include <stdio.h>

void insertionSort(int array[], int size) {
  for (int step = 1; step <= size-1; step  ) {
    int key = array[step];
    int j = step - 1;

    while (key < array[j] && j >= 0) {
      array[j   1] = array[j];
      --j;
    }
    array[j   1] = key;
  }
}

int main()
{
  int i, low, high, mid, n, key, array[100],size;
  printf("Enter number of elements: ");
  scanf("%d",&n);
  printf("Enter %d integers: ", n);
  for(i = 0; i <= n-1; i  )
    scanf("%d",&array[i]);
  insertionSort(array, n);
  printf("Enter key: ");
  scanf("%d", &key);
  low = 0;
  high = n - 1;
  mid = (low high)/2;
  while (low <= high) {
    if(array[mid] < key)
      low = mid   1;
    else if (array[mid] == key) {
      printf("%d found at %d\n", key, mid 1);
      break;
    }
    else
      high = mid - 1;
    mid = (low   high)/2;
  }
  if(low > high)
    printf("%d not found\n", key);
  return 0;
}