Comparing between a number and array

Question

I am trying to compare a number with an array containing some certain unknown values, and I want to get the number of integers which are less than the compared number.

For example:

The array would be: -2 5 2 5 7 9 10

Compared Number is: 8

Answer: 5

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

long long data[200000] = { 0 };

int cmpfunc(const void *a, const void *b) {
    return (*(long long*)b - *(long long*)a);
}

int main() {
    int numbers, i, j, z, counter, testcases;
    long long check;
    scanf("%d", &numbers);
    for (i = 0; i < numbers; i++)
        scanf("%lld", &data[i]);

    qsort(data, numbers, sizeof(long long), cmpfunc);

    scanf("%d", &testcases);
    for (j = 0; j < testcases; j++) {
        scanf("%lld", &check);
        counter = numbers;
        
        for (z = 0; z < numbers; z++) {
            if (check >= data[z])
                break;
            counter--;
        }
        printf("%d\n", counter);
    }
}

My program still runs slower than the requirement allows me, is there any way to make this faster?

Answer 1

There are some issues with your approach:

• the comparison function does not work correctly if the difference of the 2 numbers exceeds the range of type int, which is easy to achieve even with int values, eg: comparing INT_MAX and INT_MIN. You should instead use this:

    int cmpfunc(const void *aa, const void *bb) {
        const long long *a = aa;
        const long long *b = bb;
        return (*a > *b) - (*a < *b);
    }
  

• sorting the values is not always necessary for your goal: it is only useful if the number of lookups is greater than log2(N) as sorting the array takes time proportional to N.log(N).

• furthermore, you should take advantage of the sorting, using binary search to locate the number potential position and determine the count directly from that position. The current approach using linear search works the same with a sorted and unsorted array.

• unless it is part of the assignment, 200000 might not be enough for all test cases. Allocating the array seems a better approach.

Here is a modified version:

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

int cmpfunc(const void *aa, const void *bb) {
    const long long *a = aa;
    const long long *b = bb;
    return (*a > *b) - (*a < *b);
}

int main() {
    int numbers, i, j, z, counter, testcases;
    long long *data;
    long long check;

    if (scanf("%d", &numbers) != 1)
        return 1;
    data = calloc(sizeof(*data), numbers);
    if (!data)
        return 1;
    for (i = 0; i < numbers; i++) {
        if (scanf("%lld", &data[i]) != 1)
            return 1;
    }
    if (scanf("%d", &testcases) != 1)
        return 1;

    if (testcases < 63 && (1ULL << testcases) < numbers) {
        for (j = 0; j < testcases; j++) {
            if (scanf("%lld", &check) != 1)
                return 1;
            counter = 0;
            
            for (z = 0; z < numbers; z++) {
                counter += (check < data[z]);
            }
            printf("%d\n", counter);
        }
    } else {
        qsort(data, numbers, sizeof(*data), cmpfunc);
        for (j = 0; j < testcases; j++) {
            if (scanf("%lld", &check) != 1)
                return 1;

            size_t a = 0, b = numbers;
            while (a < b) {
                size_t m = a + (b - a) / 2;
                if (data[m] < check)
                    a = m + 1;
                else
                    b = m;
            }
            counter = b;
            printf("%d\n", counter);
        }
    }
    free(data);
    return 0;
}

Answer 2

Binary vs. linear

Rather than a linear search

    for (z = 0; z < numbers; z++) {
        if (check >= data[z])
            break;
        counter--;
    }

Use a binary one

    found = false;
    int lo = 0;
    int hi = numbers - 1;
    while (lo <= hi) {
      int mid = (hi-lo)/2 + lo;
      if (data[mid] < check) lo = mid + 1;
      else if (data[mid] > check) hi = mid - 1;
      else {
        found = true;
        // found it!
        // Now look for first index less than check with TBD code.
      }
    }  
         
    // Value of lo, hi  can be use to determine the count. 

Avoid overflow

*(long long*)b - *(long long*)a may overflow.

int cmpfunc(const void *a, const void *b) {
  // return (*(long long*)b - *(long long*)a);
  return (*(long long*)b > *(long long*)a) - (*(long long*)b < *(long long*)a);
}