使用insertion sort结合binary search查找值的C语言代码运行异常求助

核心问题列表 #

• 函数定义位置错误：C标准不允许在main()函数内部定义其他函数，你将insertionSort写在了main内部，属于语法错误，部分编译器会直接忽略该函数定义，导致无法调用。
• 未主动调用排序函数：你仅定义了插入排序函数，没有在输入数组后执行调用逻辑，排序自然不会生效。
• 插入排序逻辑存在数组越界风险：判断条件while (key < array[j] && j >= 0)顺序错误，若j为-1时会先访问非法内存array[j]引发崩溃，需将j >= 0前置利用逻辑与的短路特性规避越界。
• 输入输出逻辑错误：
  • 未输入目标值就提前打印未初始化的key变量，会输出乱码
  • 查找成功的打印语句格式符数量与参数不匹配，无法输出目标值的位置
  • 查找失败的提示信息不明确，仅打印目标值无法判断是否查找失败
  • 数组输入提示语句拼写错误，多了个多余的n缺少换行符

修复后的完整代码 #

#include <stdio.h>

// 插入排序函数移到main外定义
void insertionSort(int array[], int size) {
    for (int step = 1; step <= size-1; step++) {
        int key = array[step];
        int j = step - 1;
        // 调整判断条件顺序，避免越界
        while (j >= 0 && key < array[j]) {
            array[j + 1] = array[j];
            --j;
        }
        array[j + 1] = key;
    }
}

int main()
{
    int i, low, high, mid, n, key, array[100];
    printf("Enter number of elements: ");
    scanf("%d",&n);
    // 修正输入提示的拼写错误
    printf("Enter %d integers\n", n);
    for(i = 0; i <= n-1; i++) {
        scanf("%d",&array[i]);
    }
    // 主动调用插入排序
    insertionSort(array, n);
    
    printf("Enter the value to find: ");
    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 position %d\n", key, mid+1);
            break;
        }
        else
            high = mid - 1;
        mid = (low + high)/2;
    }
    if(low > high)
        // 修正查找失败的提示
        printf("%d is not present in the array\n", key);
    return 0;
}

内容的提问来源于stack exchange，提问作者Zulkar Nain Sayeed