总线错误：在C二进制和线性搜索程序中为10

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