Реализация бинарного поиска по массиву структур упорядоченных пар

Question

Я пишу некоторый код для домашнего задания, которое включает в себя получение списка упорядоченных пар, сортировку их в порядке возрастания сначала по x и по идентичным значениям x сортировку точек по возрастанию по порядку y. Я успешно выполнил это и не имею проблем. Предположим, у меня есть отсортированный массив упорядоченных парных структур.

Мне нужно получить входные данные от пользователя в виде упорядоченной пары и выполнить двоичный поиск, чтобы определить, существует ли упорядоченная пара пользователя в моем массиве. Однако мое понимание бинарного поиска распространяется только на массивы целых, а не на структуры.

Нужно ли использовать бинарный поиск, чтобы найти все упорядоченные пары, которые имеют то же значение x, что и пользователь, и только затем выполняют поиск среди этих упорядоченных пар для сопоставления у-значение?

Глядя на то, что я написал для бинарного поиска в прошлом, я сравниваю середину моего массива с тем, что я ищу, однако это сравнение разбивается на упорядоченные пары. Я не могу сказать, что одна упорядоченная пара «меньше» или «больше» другой, если я не сломаю ее.

typedef struct ordPair {
        int x, y;
} point;
...

int main(void){
...
pointArray = (point*)malloc(numOfPoints * sizeof(point));
...
}

Я ожидаю, что результаты моего поиска вернут место i, для которого pointArray [i] эквивалентно точке, отправленной пользователем, в противном случае он вернет -1.

Answer 1

У ваших структур уже есть порядок, определенный следующим образом:

Для структур A и B:

• если Ax> Bx, то A больше
• если Ax
• , если Ax == Bx, то:
  • , если Ay> к тому, что A больше
  • , если Ay
  • если Ay == К тому времени A и B эквивалентны

Поэтому, когда вы выполняете бинарный поиск, используйте приведенное выше, чтобы определить, является ли одна структура больше, меньшечем или равно другому.

Answer 2

Вы можете использовать ту же функцию сравнения для сортировки ссылочного массива с помощью qsort() и поиска в отсортированном массиве с помощью bsearch():

int point_cmp(const void *a, const void *b) {
    const pair *aa = a;
    const pair *bb = b;
    if (aa->x == bb->x)
        return (aa->y > bb->y) - (aa->y < bb->y);
    else
        return (aa->x > bb->x) - (aa->x < bb->x);
}

Вы получите индекс совпадения, вычтя массивадрес из указателя, возвращаемый bsearch(), если он успешен:

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

typedef struct ordPair {
    int x, y;
} point;

int point_cmp(const void *a, const void *b) {
    const pair *aa = a;
    const pair *bb = b;
    if (aa->x == bb->x)
        return (aa->y > bb->y) - (aa->y < bb->y);
    else
        return (aa->x > bb->x) - (aa->x < bb->x);
}

...

int main(void) {
    size_t numOfPoints;
    ...
    point *pointArray = malloc(numOfPoints * sizeof(point));
    ...
    qsort(pointArray, numOfPoints, sizeof(point), point_cmp);
    ...
    point userInput;
    ...
    point *p = bsearch(userPoint, pointArray, numOfPoints, sizeof(point), point_cmp);
    if (p != NULL) {
        // point was found: compute the index
        size_t found_index = p - pointArray;
        ...
    }
    ...
}

Answer 3

Однако мое понимание бинарного поиска распространяется только на массивы целых, а не на структуры.

Алгоритм двоичного поиска не относится к какому-либо конкретному типу данных. Требуется только полное упорядочение объектов для поиска (что требует их сортировки) и их упорядочение в этом порядке. Возможно, вы реализовали это только за int с в прошлом, но я склонен думать, что одной из целей этого упражнения является демонстрация общей применимости алгоритма двоичного поиска. Он работает для структур точно так же, как и для int с, при условии, что у вас есть подходящее средство для вычисления относительного порядка пар структур - и вы делаете , потому что вам нужно просто такая вещь для выполнения своего рода.

Глядя на то, что я написал для бинарного поиска в прошлом, я сравниваю середина моего массива с тем, что я ищу, однако, что сравнение упало для упорядоченных пар.

Нет, это не так. Вы не можете выполнить сравнение со встроенными реляционными операторами С, но это не значит, что вы не можете сравнивать.

Я подозреваю, что вы слишком сосредоточены на конкретной прошлой реализации. Я надеюсь, что вас сначала обучили алгоритму, и только потом показали или побудили найти реализацию для int s. Задача определяет соответствующий порядок упорядоченных пар. Используйте это.

Я не могу сказать, что один заказанная пара «меньше» или «больше» другого, если я не сломаю это вниз.

Ну да, вам нужно посмотреть на компоненты каждой пары, чтобы определить, какая из них "меньше". Так? Детали того, как вы принимаете это решение, не имеют значения, если вы получите правильный ответ. Это никоим образом не мешает реализации бинарного поиска, равно как это не делало (или должно было сделать) для реализации сортировки. Действительно, если вы написали функцию сравнения для использования в сортировке, то вы сможете повторно использовать эту же функцию для выполнения сравнений в бинарном поиске.