Почему эта программа двоичного поиска строки не может искать половину данных? - PullRequest
Новая
       7

Почему эта программа двоичного поиска строки не может искать половину данных?

0 голосов
/ 02 апреля 2020

Сначала я думал, что программа работает нормально, но когда я проверял, чтобы найти «лошадь», поиск не удался. И я заметил, что программа могла искать только до половины данных. Кто-нибудь знает почему? Я добавил 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;
}

Ответы [ 2 ]

2 голосов
/ 02 апреля 2020

с 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;
}
1 голос
/ 02 апреля 2020

Как указано выше, бинарный поиск предназначен для отсортированных данных. Ваш явно не отсортирован. Итак, прежде всего, вы должны отсортировать свои данные. Существует множество алгоритмов сортировки данных, но в приведенном ниже коде я использую быструю сортировку, которая также поможет вам понять ваш алгоритм поиска. 

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

После сортировки вы можете использовать алгоритм поиска.

...