Implementing binary-search on an array of ordered-pair structs

Question

I'm writing some code for a homework assignment that involves receiving a list of ordered-pairs, sorting them in ascending x-order first, and for identical x-values sort the points by ascending y-order. I've successfully accomplished that and have no issue. Assume that I have an array of ordered-pair structs sorted.

I need to receive input from the user in the form of an ordered-pair, and perform binary-search to determine if the user's ordered-pair exists in my array. However, my understanding of binary-search only extends to arrays of ints, not structs.

Do I need to use binary-search to find all ordered-pairs that have the same x-value as the user and only then search among those ordered-pairs for matching y-values?

Looking at what I've written for binary-search in the past I compare the middle of my array with what I'm searching for, however that comparison falls apart for ordered-pairs. I cannot say that one ordered-pair is "less than" or "greater than" another, unless I break it down.

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

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

I'm expect the output of my search to return the place i for which pointArray[i] is equivalent to the user submitted point, otherwise it'll return -1.

Answer 1

You can use the same comparison function to sort the reference array with qsort() and search the sorted array with 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);
}

You will get the index of the match by subtracting the array's address from the pointer returned by bsearch() if it succeeds:

#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 2

However, my understanding of binary-search only extends to arrays of ints, not structs.

The binary search algorithm is not specific to any particular data type. It requires only that there be a total ordering of the objects to be searched (which sorting them also requires), and for them to be arranged in that order. You may have implemented it only for ints in the past, but I'm inclined to think that among the purposes of the exercise is to drive home the generic applicability of the binary search algorithm. It works for structs just the same as it does for ints, as long as you have a suitable means by which to compute the relative order of pairs of structs -- and you do, because you needed just such a thing to perform your sort.

Looking at what I've written for binary-search in the past I compare the middle of my array with what I'm searching for, however that comparison falls apart for ordered-pairs.

No, it doesn't. You cannot perform the comparison with C's built-in relational operators, but that does not mean you cannot compare.

I suspect that you're focusing too much on a specific past implementation. I would hope that you were first taught the algorithm, and only then shown or induced to discover an implementation for ints. The problem defines an appropriate ordering of the ordered pairs. Use it.

I cannot say that one ordered-pair is "less than" or "greater than" another, unless I break it down.

Well yes, you need to look at the components of each pair to determine which one is "less". So? The details of how you make that determination don't matter, as long as you get the right answer. This in no way interferes with implementing binary search, any more than it did (or should have done) for implementing the sorting. Indeed, if you wrote a comparison function for use in the sorting, then you should be able to re-use the same function for performing comparisons in the binary search.

Answer 3

Your structs already have an ordering defined as follows:

For structs A and B:

• if A.x > B.x then A is greater
• if A.x < B.x then B is greater
• if A.x == B.x then:
  • if A.y > B.y then A is greater
  • if A.y < B.y then B is greater
  • if A.y == B.y then A and B are equivalent

So when you perform your binary search, use the above to determine whether one struct is greater than, less than, or equal to another.