为什么这个字符串二进制搜索程序不能搜索一半的数据？

Question

起初，我以为程序可以正常运行，但是当我测试搜索“马”时，它搜索失败。而且我注意到该程序最多只能搜索一半的数据。有人知道为什么吗？我已经添加了qsort，但是它仍然不会搜索数据的下半部分。

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

int compare(const void *a, const void *b){

    const char *ia = (const char *)a;
    const char *ib = (const char *)b;

    return strcmp(ia, ib);
}

int main(int argc, char argv){

    char data[10][50]={"cow", "goat", "dog", "sheep", "chicken", "duck", "bird","fish", "bee", "horse"};
    int size1 = sizeof(data[0]);
    int n = sizeof(data) / size1;
    printf("%d\n\n", n);
    int i, j;
    bool check = false;
    char key[10];
    int low = 0;
    int high = n - 1;
    int mid;
    char temp;

    for(i = 0; i<n; i++){
        printf("%s\n", data[i]);
    }

    qsort(data, n, size1, compare);
    printf("=============\n\n");

    for(i = 0; i<n; i++){
        printf("%s\n", data[i]);
    }
    system("pause");
    printf("Search: "); scanf("%s", &key);
    fflush(stdin);

    while(low<=high){
        mid = (low + high) / 2;
        if(strcmp(key,data[mid])==0){
            printf("Data Found ! on index - %d\n", mid);
            break;
        } else if(strcmp(key,data[mid])<0){
            low = mid + 1;
        }else {
            high = mid - 1;
        }
    }

    if(low > high){
        printf("Data not found");
    }
    return 0;
}

Answer 1

使用qsort，您可以对字符串数组进行排序，而且正如我在下面的代码中显示的，在这里else if (strcmp(key, data[mid]) < 0)应该是>。否则您的搜索将无法进行。

static int myCompare(const void* a, const void* b)
{
    return strcmp(*(const char**)a, *(const char**)b);
}

int main()
{
    char* data [] = { 
        "cow", "goat", "dog", "sheep", "chicken", "duck", "bird","fish", "bee", "horse" 
    };
    int n = sizeof(data) / sizeof(data[0]);
    int i;

    qsort(data, n, sizeof(const char*), myCompare);
    char key[10];
    int low = 0;
    int high = n - 1;
    int mid;
    char temp;

    scanf("%s", key);
    fflush(stdin);

    while (low <= high) {
        mid = (low + high) / 2;
        int a = strcmp(key, data[mid]);
        if (a == 0) {
            printf("Data Found ! on index - %d\n", mid);
            break;
        }
        else if (a > 0) {
            low = mid + 1;
        }
        else { // or only else(no special need for else if
            high = mid - 1;
        }
    }

    if (low > high) {
        printf("Data not found");
    }
    return 0;
}

Answer 2

如上所述，二进制搜索用于排序的数据。您的显然没有排序。因此，首先，您必须对数据进行排序。有很多用于对数据进行排序的算法，但是下面的代码中，我使用了快速排序，这也将帮助您理解您的搜索算法。

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

void swap(char ** a, char ** b) { 
    char * t = *a;
    *a = *b;
    *b = t;
}


/* This function takes last element as pivot, places 
   the pivot element at its correct position in sorted 
    array, and places all smaller (smaller than pivot) 
   to left of pivot and all greater elements to right 
   of pivot */
int partition (char ** arr, int low, int high) { 
    char * pivot = arr[high];    // pivot 
    int i = (low - 1);  // Index of smaller element 

    for (int j = low; j <= high- 1; j++) { 
        // If current element is smaller than the pivot 
        if (strcmp(arr[j],pivot) < 0) { 
            i++;    // increment index of smaller element 
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
}

/* arr[] --> Array to be sorted, 
   low  --> Starting index, 
   high  --> Ending index */
void quickSort(char **arr, int low, int high) { 
    if (low < high) { 
        /* pi is partitioning index, arr[p] is now 
           at right place */
        int pi = partition(arr, low, high); 

        // Separately sort elements before 
        // partition and after partition 
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
} 

int main(){

   char *a = "abc";
   char *b = "cdf";
   swap(&a, &b);
   printf("a = %s, b= %s\n", a, b);
   char * data[10]={"cow", "goat", "dog", "sheep", "chicken", "duck", "bird","fish", "bee", "horse"};
   quickSort(data, 0, 9);
   for(int i = 0; i < 10; i++) {
    printf("%s, ", data[i]);
   }

   return 0;
}

排序后，您可以使用搜索算法。