Как использовать структуры в бинарном поиске? - PullRequest
Новая
       10

Как использовать структуры в бинарном поиске?

0 голосов
/ 12 февраля 2019

Я пытаюсь выучить c (это мой родной язык), и у меня есть некоторые проблемы с этой задачей.(Это не домашняя работа!)

Задание:

Реализация алгоритма двоичного поиска по массиву структур следующего вида (извините за мой английский). 

    struct {
    unsigned int number;
    char* food;
    int price; 
} pk;
  • Данный массив отсортирован в порядке возрастания
  • Когда найденный номер найден, вернуть <nr>: <food> <price>\n назад
  • Если искомый номер не найден, вернуть <nr> is not in pk \nи вернуть -1

Мой код: 

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


struct {
    unsigned int number;
    char* food;
    int price; 
} pk;


int binary search(int pk[], int l, int r, unsigned int number){
    int center;
    int start = l;
    int end = r;

    if (start == end){
        if (pk[start] == number){
            printf ("%d is in pk\n", number);   // do not know how to use the struct 
        }else{
            printf ("%d is not in pk\n", number);
            return -1;
        }
    }
    else {
        center = (start + end)/2;
        if (number <= pk[center]){
            return binary search(pk, start, center, number);
        }else{
            return binary search(pk, center+1, end, number);
        }
    }
}

Мои вопросы:
1) Может ли этот код работать?
2) Как я могу использовать эту структуру длявыполнить задание, по моему мнению, я должен выполнить его иначе, чем сейчас.

1 Ответ

0 голосов
/ 12 февраля 2019

Включить все предупреждения компилятора!

Когда if (start == end){ if (pk[start] == number){ истинно, код возвращает ничего .

Я бы ожидал return start; в этом случае.

Избегайте start + end переполнения 

// center = (start + end)/2;
center = start + (end - start)/2;

Немного иначе:
Я бы рекомендовал возвращать указатель на массив при успехе и NULL при ошибке 

// int binary search(pk a[], int l, int r, unsigned int number){
pk *binary search(pk a[], int l, int r, unsigned int number){
    int start = l;
    int end = r;

    if (start == end){
        if (a[start].number == number){
            printf ("%d is in a[] at index\n", number, start);
            return &a[start];
        }else{
            printf ("%d is not in a[]\n", number);
            return NULL;
        }
    }
    else {
        int center = start + (end - start)/2;
        if (number <= a[center].number){
            return binary search(a, start, center, number);
        }else{
            return binary search(a, center+1, end, number);
        }
    }
}

Дополнительно: лучший код будет использовать size_t для индексации и const a[]

pk *binary search(const pk a[], size_t l, size_t r, unsigned int number){
...