带插入排序的二分查找

Question

将使用使用插入排序的二分搜索来查找值。编码新手，所以找不到解决方案。现在，如果我输入任何值，它不会使用插入，也找不到该值。

#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;
}

Answer 1

问题是在输入元素后从未在数组上调用 insertionSort。相反，您在应该调用函数的地方定义了函数 insertionSort。在另一个函数中定义一个函数不是 C 语言的标准部分，但某些编译器可能支持它作为扩展。

如果将 insertionSort 的定义移到 main 函数之外，并添加对该函数的调用，则代码会在修复一些 printf 语句后运行。这是一个稍微整理过的工作版本：

#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;
}

Answer 2

我更正了你的代码。

#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;
}

我发现的问题是：

该函数在 main 内部（记住它不能完成），如果前面有声明，您可以将它放在 main 之后，或者将它放在 main 之前。
插入排序中的 for guard 是错误的，你必须输入 step < size 而不是 step <= size - 1
如你所想每次在for中循环都要调用插入，只需要在数组中插入所有元素后调用一次即可
你在扫描之前放置了 kay 的 printf，这会打印出随机的东西，因为变量的内容不干净。

希望有所帮助。

带插入排序的二分查找

binary search with insertion sort

c

binary-search

insertion-sort