c - 总线错误 : 10 in C binary and linear search program

Question

#include <stdio.h>
#include <stdlib.h>

void arrayCopy(int fromArray[], int toArray[], int size){
    int i = 0;

    while(i < size){
        toArray[i] = fromArray[i];
        i++;
    }
}


void sort(int arr[], int size){
    int i, j;
    int temp;

    //simple sorting method comparing values next to each other
    //bigger value is moved further down the array
    //loops through "size" times
    for(i = 0; i < size; i++){
       for(j = 0; j < size - 1; j++){
            if(arr[j] > arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int linSearch(int arr[], int size, int target, int* numComparisons){
    int i;
    *numComparisons = 0;

    //if target is found loop will exit prematurely returning location in array
    //if target is not found loop will exit and return -1
    for(i = 0; i < size; i++){
        *numComparisons = *numComparisons + 1;  //tracks number of comparisons made
        if(arr[i] == target){
            return i;
        }
    }
    return -1;
} 

int binSearch(int arr[], int size, int target, int* numComparisons){
    int i;
    int first, last, mid;

    first = 0;
    last = size - 1;
    mid = (first + last) / 2;
    *numComparisons = 0;

    while(first <= last){
        if(arr[mid] == target){
            *numComparisons = *numComparisons + 1;
            return mid;
        } else if(arr[mid] < target){
            *numComparisons = *numComparisons + 1;
            first = mid + 1;
        } else{
            *numComparisons = *numComparisons + 1;
            last = mid - 1;
        }
    }

    return -1;


}

int main(){
    int i = 0;
    int j, k, l;
    int size = 0;
    int dynamicSize = 100;
    int val;
    int *arr1, *arr2;
    int *temp;
    int *numComparisons1, *numComparisons2;


    arr1 = (int*)malloc(dynamicSize * sizeof(int));

    printf("Please input your values.\n Terminate input with the value -999.\n");

    while(val != -999){
        //reads values and assigns them to array
        scanf("%d", &val);
        if(size >= dynamicSize){
            temp = (int*)malloc(dynamicSize * 2 * sizeof(int));
            for ( i = 0 ; i < dynamicSize ; i++){
                temp[i] = arr1[i];
            }
            free(arr1);
            arr1 = temp;
            dynamicSize = dynamicSize * 2;
        }
        arr1[i] = val;
        i = i + 1;
        size = size + 1;

    }
    val = 0;

     //Second array for binary search
     arr2 = (int*)malloc(dynamicSize * sizeof(int));
     arrayCopy(arr1, arr2, size);
     sort(arr2, size);

    printf("Please enter the number you would like to find.\n Terminate search with value -999.\n");
    while(val != -999){
        scanf("%d", &val);
        k = linSearch(arr1, size, val, numComparisons1);
        j = binSearch(arr2, size, val, numComparisons2);
        if(k == -1){
             printf("The value was not found.\n");
        }else{
             printf("Unsorted Array:\n The value is located at %d\n The number of comparisons made was %d\n", k, *numComparisons1);
             printf("Sorted Array:\n The value is located at %d\n The number of comparisons made was %d\n", j, *numComparisons2);
    }
  }

    return 0;
}

该程序应该接收用户输入并将其存储在一个数组中。当用户输入值 -999 时，程序将创建第二个数组，它是第一个数组的副本。然后将通过排序函数对第二个数组进行排序，以便在二进制搜索函数中使用。该程序然后要求用户输入一个值，该值将通过线性搜索和二分搜索进行检查。如果找到该值，函数将返回进行的比较次数以及该值在数组中的位置。如果未找到，程序将返回未找到该值。重复此过程，直到用户通过输入值 -999 终止程序。问题似乎出在二进制搜索上。当包含该程序时，它会产生总线错误:10，但是当我注释掉对 binSearch 函数的调用时，该程序运行正常。

Answer 1

您应该在将值存储到数组中之前检查可用空间:

int *arr1 = malloc(sizeof(int));
size_t dynamicSize = 1;
size_t size = 0;

// reads values and assigns them to array
while (scanf("%d", &val) == 1 && val != -999) {
    if (size >= dynamicSize) {
        arr1 = realloc(arr1, dynamicSize * 2 * sizeof(*arr1));
        dynamicSize = dynamicSize * 2;
    }
    arr1[size++] = val;
}

您的二进制查找函数不正确:

• 您必须为循环中的每次迭代重新计算 mid
• 您没有正确计算比较次数
• 您在 mid 的计算中遇到了典型的算术溢出错误

修改后的版本:

int binSearch(int arr[], int size, int target, int *numComparisons) {
    int first = 0;
    int last = size;
    int comp = 0;

    while (first < last) {
        int mid = first + (last - first) / 2;

        comp++;
        if (arr[mid] == target) {
            *numComparisons = comp;
            return mid;
        }
        comp++;
        if (arr[mid] < target) {
            first = mid + 1;
        } else {
            last = mid;
        }
    }
    *numComparisons = comp;
    return -1;   
}