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?
CodePudding user response:
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 withint
values, eg: comparingINT_MAX
andINT_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
log(N)
and you should take advantage of the sorting, using binary search to locate the number potential position and determine the count directly from that position.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 < 31 && (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;
}
CodePudding user response:
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);
}