總線錯誤：在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; 
}